枚举对第一行的操作，根据操作后的状态确定之后每一行如何操作，记录最小的操作次数即为答案
1 #include <iostream>
2 using namespace std;
3 const int OO=100000000;
4 const int s[5][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0}};
5 bool map[6][6];
6 bool g[6][6];
7 int ans=OO;
8
9 void change(int a,int b){
10 for (int i=0;i<5;++i){
11 int x=a+s[i][0],y=b+s[i][1];
12 g[x][y]=1-g[x][y];
13 }
14 }
15
16 void work(int x,bool white){
17 for (int i=1;i<=4;++i)
18 for (int j=1;j<=4;++j) g[i][j]=map[i][j];
19 bool list[5];
20 for (int i=1;i<=4;++i){
21 if (x%2) list[i]=true;
22 else list[i]=false;
23 x/=2;
24 }
25 int num=0;
26 for (int i=1;i<=4;++i) if (list[i]){
27 change(1,i);
28 ++num;
29 }
30
31 for (int i=2;i<=4;++i)
32 for (int j=1;j<=4;++j) if (g[i-1][j]!=white){
33 change(i,j);
34 ++num;
35 }
36 bool ok=true;
37 for (int i=1;i<=4;++i) if (g[4][i]!=white){
38 ok=false;
39 break;
40 }
41 if (ok&&num<ans) ans=num;
42 }
43
44 int main(){
45 for (int i=1;i<=4;++i){
46 for (int j=1;j<=4;++j){
47 char ch=getchar();
48 if (ch=='b') map[i][j]=true;
49 }
50 char ch=getchar();
51 }
52 for (int i=0;i<16;++i){
53 work(i,true);
54 work(i,false);
55 }
56 if (ans<OO) cout<<ans;
57 else cout<<"Impossible";
58 }
59
posted on 2008-11-07 19:21
Joseph 阅读(194)
评论(0) 编辑 收藏 引用