#include<stdio.h> #include<math.h> #include<algorithm> #include<string.h> using namespace std; int pieces[10][10]; int ans[16]; int res[4][4]; int Min=1000000; const int INF=1<<16; char ary[10]; void AddOne(int a[]) { int i=0; while(i<16) { a[i]+=1; if(a[i]<2) break; a[i]=0; i++; } } bool isBorW() { int i,j; int c=0; for(i=0;i<4;i++) { for(j=0;j<4;j++) { res[i][j]=pieces[i][j]; } } for(i=0;i<16;i++) { if(ans[i]==1) { c++; int m=i/4; int n=i%4; res[m][n]=1^res[m][n]; if(m-1>=0) res[m-1][n]=1^res[m-1][n]; if(m+1<4) res[m+1][n]=1^res[m+1][n]; if(n-1>=0) res[m][n-1]=1^res[m][n-1]; if(n+1<4) res[m][n+1]=1^res[m][n+1]; } } for(i=0;i<4;i++) { for(j=0;j<4;j++) { if(res[i][j]!=res[0][0]) { return false; } } } Min=Min>c?c:Min; return true; } void print() { int i; for(i=0;i<16;i++) { printf("%d",ans[i]); } printf(" "); } int main() { int i,j; for(i=0;i<4;i++) { gets(ary); for(j=0;j<4;j++) { if(ary[j]=='b') pieces[i][j]=1; else pieces[i][j]=0; } } memset(ans,0,sizeof(ans)); for(i=0;i<INF;i++) { isBorW(); // print(); AddOne(ans); } if(Min<=16) printf("%d ",Min); else printf("Impossible "); return 0; } /* bbww bwww wwww wwww bbww bwbw wbbb wwbw bwwb bbwb bwwb bwww */
枚举0~2^16的所有数字，每一位代表该位上的棋子是否翻转。同样的思想，可以不用AddONE函数
#include<stdio.h> #include<math.h> #include<algorithm> #include<string.h> using namespace std; const int INF=1<<16; int pieces[10][10]; int res[10][10]; int MIN=1000000; void fun(int tmp) { int ans[20]; int i=0,count=0,j; memset(ans,0,sizeof(ans)); while(tmp) { ans[i]=tmp%2; tmp/=2; i++; } for(i=0;i<4;i++) { for(j=0;j<4;j++) { res[i][j]=pieces[i][j]; } } for(i=0;i<16;i++) { if(ans[i]==1) { int m,n; count++; m=i/4; n=i%4; res[m][n]=res[m][n]^1; if(m-1>=0) { res[m-1][n]=res[m-1][n]^1; } if(m+1<4) { res[m+1][n]=res[m+1][n]^1; } if(n+1<4) { res[m][n+1]=res[m][n+1]^1; } if(n-1>=0) { res[m][n-1]=res[m][n-1]^1; } } } for(i=0;i<4;i++) { for(j=0;j<4;j++) { if(res[i][j]!=res[0][0]) return; } } MIN=MIN<count?MIN:count; } int main() { char str[10]; int i,j; for(i=0;i<4;i++) { gets(str); for(j=0;j<4;j++) { if(str[j]=='b') pieces[i][j]=1; else pieces[i][j]=0; } } for(i=0;i<INF;i++) { fun(i); } if(MIN<=16) { printf("%d ",MIN); } else { printf("Impossible "); } return 0; } /* bwwb bbwb bwwb bwww bbww bwbw wbbb wwbw */