POJ 3279 Fliptile 反转（二进制枚举）

痛定思痛。 2024-02-17 19:06 85阅读 0赞

题意：有一个n\*m的格子，每个格子都有黑白两面（0表示白色，1表示黑色）。我们需要把所有的格子都反转成白色，每反转一个格子，它上下左右的格子都会跟着反转。请求出用最小步数完成反转时每个格子反转的次数。有多个解时，输出字典序最小的一组。

思路：二进制枚举第一行，然后逐行向下进行判断，从第二行（row）起，当row的第k列的上一行有黑色（1），则必须翻转chang(row,k)，保证满足上一行全白色（0）；当所有行全部判断完成之后，只需在检查最后一行有无黑色（1），无则满足条件

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=15+2;
    int g[maxn][maxn],d[maxn][maxn],new1[maxn][maxn]; //输入存入g,g复制到new1，d保存最终输出每个格子的反转数 
    int M,N;
    int min1;
    int dir[][2]={
       {1,0},{-1,0},{0,-1},{0,1},{0,0}};
    void chang(int row,int col){
    	for(int i=0;i<5;i++){
    		int x=dir[i][0]+row;
    		int y=dir[i][1]+col;
    	 if(x>=0&&x<M && y>=0&&y<N){
    	 	new1[x][y]=1-new1[x][y];
    	  }
    	}
    }
    void solve(){
    	int count=0;     //用于判断最后能否输出d(>0则可以) 
    	for(int i=0;i<(1<<N);i++){
    		int total=0;
    		int d1[maxn][maxn]; 
    		memset(d1,0,sizeof(d1));
    		memcpy(new1,g,sizeof(g));
    		for(int j=0;j<N;j++){
    			if(i&(1<<j)){
    			chang(0,j);
    			d1[0][j]=1;
    			total++;
    			}
    		}
    		
    		for(int j=1;j<M;j++){
    			for(int k=0;k<N;k++){
    				if(new1[j-1][k]==1){
    					chang(j,k);
    					d1[j][k]=1;
    					total++;
    				}
    			}
    		}
    		int flag=1;
    		for(int j=0;j<N;j++)
    				if(new1[M-1][j]==1)
    				{flag=0;break;}
    		
    		if(flag){
    			count++;
    			if(min1>total){
    				memcpy(d,d1,sizeof(d1));
    				min1=total;
    			}
    			else if(min1==total){
    				int ok=0;
    				for(int j=0;j<M;j++)
    				 for(int k=0;k<N;k++){
    				 	if(d1[j][k]<d[j][k]){
    				 		j=M;k=N;ok=1;
    					 }
    					 else if(d1[j][k]>d[j][k]){
    					 	j=M;k=N;
    					 }
    				 }
    				 if(ok) memcpy(d,d1,sizeof(d1));
    			}
    		}
    	}
    	if(!count)printf("IMPOSSIBLE\n");
    	else for(int i=0;i<M;i++){
    		printf("%d",d[i][0]);
    	        for(int j=1;j<N;j++)
    	        printf(" %d",d[i][j]);
    	        printf("\n");
    	}
    }
    int main(){
    	while(scanf("%d%d",&M,&N)==2){
    		for(int i=0;i<M;i++)
    		 for(int j=0;j<N;j++)
    		  scanf("%d",&g[i][j]);
    		  min1=maxn*maxn;
    		  solve();
    	} 
    	return 0;
    }