POJ-1753

题目链接：http://poj.org/problem?id=1753

题目概述：有4*4的正方形，每个格子要么是黑色，要么是白色，当把一个格子的颜色改变(黑->白或者白->黑)时，其周围上下左右(如果存在的话)的格子的颜色也被反转，问至少反转几个格子可以使4*4的正方形变为纯白或者纯黑？

 1 #include"iostream"
 2 using namespace std;
 3 
 4 bool qipan[6][6]={false};
 5 bool flag;
 6 int  a[]={-1,1,0,0,0};
 7 int  b[]={0,0,-1,1,0};
 8 int step;
 9 bool panduan(){
10     for(int i=1;i<=4;i++)
11         for(int j=1;j<=4;j++)
12             if(qipan[i][j]!=qipan[1][1])
13                 return false;
14     return true;
15 }
16 void bianhuan(int c,int d){
17     for(int i=0;i<5;i++)
18         qipan[c+a[i]][d+b[i]]=!qipan[c+a[i]][d+b[i]];
19 }
20 void dfs(int row,int tow,int deep){
21     if(deep==step){
22         flag=panduan();
23         return;    
24     }
25     if(row||tow==5)
26         return;
27     bianhuan(row,tow);
28     if(row<4)
29         dfs(row,tow+1,deep+1);
30     else
31         dfs(row+1,tow,deep+1);
32     bianhuan(row,tow);
33     if(row<4)
34         dfs(row,tow+1,deep);
35     else
36         dfs(row+1,tow,deep);
37     return;
38 }
39 int main(){
40     char temp;
41     int i,j;
42     for(i=1;i<5;i++)
43         for(j=1;j<5;j++)
44         {
45             cin>>temp;
46             if(temp=='b') 
47                 qipan[i][j]=true;
48         }
49 
50     for(step=0;step<=16;step++)  //对每一步产生的可能性进行枚举
51     {                            //至于为什么是16，考虑到4x4=16格，而每一格只有黑白两种情况，则全部的可能性为2^16
52         dfs(1,1,0);
53         if(flag)break;
54     }
55 
56     if(flag)
57         cout<<step<<endl;
58     else
59         cout<<"Impossible"<<endl;
60     return 0;
61 }