poj 3297 Fliptile 深搜

柔情只为你懂 2022-08-08 05:21 149阅读 0赞

#include <cstdio>
    
    using namespace std;
    
    #define MAX 16
    int a[MAX], b[MAX], now[MAX], minb[MAX];
    int m, n;
    int dis[5][2]={ {0,1},{0,-1},{-1,0},{1,0},{0,0} };
    
    void copy(int a[], int b[])
    {
    	for(int i=0; i<20; i++) b[i]=a[i];
    }
    void rev(int x, int y)
    {
    	if(x>=0&&x<m && y>=0&&y<n){
    		now[x] ^= 1<<(y);
    	}
    }
    void change(int k, int v)
    {
    	for(int i=0; i<n; i++){
    		if( ((1<<i)&v) != 0){
    			for(int j=0; j<5; j++)	
    				rev( k+dis[j][0], i+dis[j][1] );
    		}
    	}
    }
    int find_r()
    {
    	bool flag;
    	int min=0x7fffffff;
    	for(int i=0; i<(1<<n); i++){
    		b[0]=i;
    		copy(a, now);	
    		change(0, i);
    		for(int j=1; j<m; j++){			
    			b[j] = now[j-1];
    			change(j, now[j-1]);
    		}
    		flag = true;
    		for(int j=0; j<m; j++)	{
    			if(now[j]!=0){	
    				flag=false;	break;
    			}
    		}
    		if(flag)	{
    			int w=0;
    			for(int j=0; j<m; j++){
    				for(int k=0; k<n; k++){
    					if( (b[j] & (1<<k) ) != 0)	w++;					
    				}
    			}
    			if(w<min){
    				min = w;
    				copy(b, minb);
    			}
    			
    		}
    	}	
    	return min;
    }
    void print()
    {
    	for(int i=0; i<m; i++){
    		for(int j=n-1; j>=0; j--){
    			if(j==n-1 ){
    				if(  (minb[i]&(1<<j) ) != 0 ){
    					printf("1");
    				}
    				else printf("0");
    			}
    			else{
    				if( (minb[i]&(1<<j)) != 0 ){
    					printf(" 1");
    				}
    				else printf(" 0");
    			}
    		}
    		printf("\n");
    	}
    }
    int main()
    {
    	int c;
    	int flag;	
    	while( scanf("%d%d", &m , &n)!=-1 ){
    		for(int i=0; i<20; i++)	a[i]=0;
    		
    		for(int i=0; i<m; i++){
    			for(int j=0; j<n; j++){
    				scanf("%d", &c);
    				if(c==1) a[i]+= ( 1<<(n-j-1) );
    			}
    		}
    		flag = find_r();
    		if(flag!=0x7fffffff)print();
    		else printf("IMPOSSIBLE\n");
    	}	
    	return 0;
    }