rt
枚举第一行（即对第一行的方块进行翻转），16种可能性。
翻转第二行的方块，修改对应列的第一行的方块，使得第一行全黑/白。
翻转第三行的方块，修改对应列的第二行的方块，使得第二行全黑/白。
翻转第四行的方块，修改对应列的第三行的方块，使得第三行全黑/白。
最后查看第四行是否满足全黑/白。若不满足，则"Impossible"（只要有一种枚举不满足，其它的枚举也不满足，反之，只要有一种枚举满足，则所有的枚举都满足，因为同一个方块翻转两次，整体不变，猜测所有的可行解都是可以互相转换，并都始于全黑/白，终于全黑/白），否则继续下一次枚举。

Source Code
Problem: 1753		User: victor0127
Memory: 188K		Time: 0MS
Language: C++		Result: Accepted

    Source Code

    #include<iostream>
    #include<cmath>
    #include<string>
    #include<cstdio>
    using namespace std;

    int square[4][4];
    int flipBit[4][4];

    void flip(int i, int j)
    {
    	square[i][j]=square[i][j]==1?0:1;
    	if(i<3)
    		square[i+1][j]=(square[i+1][j]==1)?0:1;
    	if(i>0)
    		square[i-1][j]=(square[i-1][j]==1)?0:1;
    	if(j<3)
    		square[i][j+1]=(square[i][j+1]==1)?0:1;
    	if(j>0)
    		square[i][j-1]=(square[i][j-1]==1)?0:1;

    }
    int main()
    {
    	int min, count,flag,i,j,k,l,m,sum;
    	string s;
    	int ts[4][4];
    	for(i=0; i<4; i++){
    		cin >> s;
    		for(j=0; j<4; j++){
    			if(s.at(j)=='w'){
    				square[i][j]=0;
    				ts[i][j]=0;
    				}
    			else{
    				square[i][j]=1;
    				ts[i][j]=1;
    			}
    		}			
    	}

    	
    	min=16;	
    	m=0;
    	for(i=0; i<16; i++){
    		j=3;
    		m=i;
    		while(m!=0){
    			flipBit[0][j]=m%2;
    			m/=2;
    			j--;
    		}
    		count=0;
    		flag=0;
    		for(k=0; k<4; k++){
    			if(flipBit[0][k]==1){
    				flip(0,k);
    				count++;
    			}
    			flag+=square[0][k];
    		}
    		if(flag>2)
    			flag=1;
    		else
    			flag=0;

    		for(k=0; k<3; k++){
    			for(l=0; l<4; l++){
    				if(square[k][l]!=flag){
    					flip(k+1,l);
    					count++;
    				}
    			}
    		}
    		if(count==0){
    			cout << 0 << endl;
    			return 0;
    		}
    		if(count<min){
    			min=count;
    		}
    		sum=0;
    		for(k=0; k<4; k++){
    			sum+=square[3][k];
    		}			
    		if(sum!=flag*4){
    			cout << "Impossible" << endl;

    			return 0;
    		}


    	for(int p=0; p<4; p++)
    		for(int q=0; q<4; q++)
    			square[p][q]=ts[p][q];

    	}
    	cout << min << endl;
    return 0;
    }

• Re:枚举第一行，用下一行的翻转改变当前行的值，判断最后一行是否满足条件。0MS。 (2534) wucheng_xidian 2012-08-30 16:56:18
• Re:枚举第一行，用下一行的翻转改变当前行的值，判断最后一行是否满足条件。0MS。 (79) troore 2013-02-26 17:25:33