題目意思說用最少的次數翻動使所有的面是白色或黑色:
思路:通過枚舉第一行的狀態（16種狀態），得出答案..
附上code:
1 #include <iostream>
2 #include <string>
3 #include <bitset>
4
5 using namespace std;
6 int map[10][10];
7 int opr[10][10];
8 int ans,zhen;
9 void hanshu(int n)
10 {
11 for(int i=0;i<16;i++){
12 int cnt=0;
13 bitset<4> bit(i);
14 for(int r=1;r<=4;r++)
15 for(int j=1;j<=4;j++)
16 opr[r][j]=map[r][j];
17 for(int r=0;r<4;r++){
18 if(bit[r]==1){
19 cnt++;
20 opr[1][r+1]^=1;
21 opr[1][r]^=1;
22 opr[2][r+1]^=1;
23 opr[1][r+2]^=1;
24 }
25 }
26 for(int r=2;r<=4;r++){
27 for(int j=1;j<=4;j++){
28 if(opr[r-1][j]==n){
29 cnt++;
30 opr[r-1][j]^=1;
31 opr[r][j-1]^=1;
32 opr[r][j]^=1;
33 opr[r][j+1]^=1;
34 opr[r+1][j]^=1;
35 }
36 }
37 }
38 bool prim=false;
39 for(int i=1;i<=4;i++){
40 if(opr[4][i]==n){
41 prim=true;
42 }
43 }
44 if(!prim&&cnt<ans){
45 zhen=0,ans=cnt;
46 }
47 }
48 }
49 int main()
50 {
51 string ss;
52 while(cin>>ss){
53 ans=0x7fffffff;
54 zhen=-1;
55 memset(map,0,sizeof(map));
56 memset(opr,0,sizeof(opr));
57 for(int i=0;i<ss.size();++i){
58 if(ss[i]=='b')map[1][i+1]=0;
59 else map[1][i+1]=1;
60 }
61 for(int i=2;i<=4;i++){
62 cin>>ss;
63 for(int j=0;j<ss.size();j++){
64 if(ss[j]=='b')map[i][j+1]=0;
65 else map[i][j+1]=1;
66 }
67 }
68 hanshu(0);
69 hanshu(1);
70 if(zhen!=-1)cout<<ans<<endl;
71 else cout<<"Impossible"<<endl;
72 }
73 return 0;
74 }
75
posted on 2008-05-15 20:22
小果子 閱讀(608)
評論(0) 編輯 收藏 引用 所屬分類:
Acm