zcmimi's blog
avatar
zc
2019-12-21 19:47:00
  • 本文总阅读量
查看原题

点击跳转

枚举哪些行和哪些列要变成回文

处理:

行:点(i,j)对应点(i,m-j+1)

列:点(i,j)对应点(n-i+1,j)

我们可以用并查集合并这些点

然后求每个块中0还是1多

#include<bits/stdc++.h>
#define il inline
#define clr(x,y) memset(x,y,sizeof x)
#define Fur(i,x,y) for(int i(x);i<=y;++i)
using namespace std;
il int min(int x,int y){return x<y?x:y;}
#define N 20
int fr[N][N],fc[N][N];
int row[N],col[N],f[N*N],cnt0[N*N],cnt1[N*N];
int r,c,n,m,ans;
char ch[N][N];
int gf(int x){return (x==f[x])?x:(f[x]=gf(f[x]));}
il void mg(int x,int y){
    int fx=gf(x),fy=gf(y);
    if(fx!=fy){
        f[fy]=fx;
        cnt0[fx]+=cnt0[fy];
        cnt1[fx]+=cnt1[fy];
    }
}
il int id(int i,int j){return (i-1)*m+j;}
void solve(){
    clr(fr,0);clr(fc,0);
    Fur(i,1,r)
        Fur(j,1,m)
            fr[row[i]][j]=1;

    Fur(i,1,n)
        Fur(j,1,c)
            fc[i][col[j]]=1;

    Fur(i,1,n)
        Fur(j,1,m)
        if(fr[i][j]||fc[i][j]){
            f[id(i,j)]=id(i,j);
            if(ch[i][j]=='0')cnt0[id(i,j)]=1,cnt1[id(i,j)]=0;
            else cnt0[id(i,j)]=0,cnt1[id(i,j)]=1;
        }
    Fur(i,1,n)
        Fur(j,1,m){
            if(fr[i][j])mg(id(i,j),id(i,m-j+1));
            if(fc[i][j])mg(id(i,j),id(n-i+1,j));
        }
    int sum=0;
    Fur(i,1,n)
        Fur(j,1,m)
        if((fr[i][j]||fc[i][j])&&f[id(i,j)]==id(i,j))
            sum+=min(cnt0[id(i,j)],cnt1[id(i,j)]);

    ans=min(ans,sum);
}
void dfs2(int cnt,int pre){
    if(cnt==c+1)return (void)solve();
    Fur(i,pre+1,m){
        col[cnt]=i;
        dfs2(cnt+1,i);
    }
}
void dfs(int cnt,int pre){
    if(cnt==r+1)return (void)dfs2(1,0);
    Fur(i,pre+1,n){
        row[cnt]=i;
        dfs(cnt+1,i);
    }
} 
int main(){
    scanf("%d%d%d",&r,&c,&n);
    Fur(i,1,n)
        scanf("%s",ch[i]+1);
    m=strlen(ch[1]+1);
    ans=(1<<30);
    dfs(1,0);
    printf("%d\n",ans);
}
51nod 1316 回文矩阵
comment评论
Search
search