复杂度不高
#include <iostream> #include <stdio.h> #include <memory.h> using namespace std; int array[5][5],t[5][5]; int bit[5]; void Getbit(int i) { int t=4; while(i!=0) { bit[t]=i%2; i=i/2; t--; } } void flip(int i,int j) { array[i][j]=array[i][j]>0?0:1; if(i-1>=1) array[i-1][j]=array[i-1][j]>0?0:1; if(i+1<=4) array[i+1][j]=array[i+1][j]>0?0:1; if(j-1>=1) array[i][j-1]=array[i][j-1]>0?0:1; if(j+1<=4) array[i][j+1]=array[i][j+1]>0?0:1; } int main() { int i,j,sum,k; int cnt,min,stand; char ch; for(i=1;i<=4;i++) { for(j=1;j<=4;j++) { scanf("%c",&ch); if(ch=='w') { array[i][j]=1; t[i][j]=1; } else { array[i][j]=0; t[i][j]=0; } } getchar(); } min=16; //1 for(k=0;k<16;k++) { cnt=0; sum=0; memset(bit,0,sizeof(bit)); Getbit(k); for(i=1;i<=4;i++) { if(bit[i]==1) { flip(1,i); //0 1 cnt++; } sum+=array[1][i]; //01 } if(sum>2) stand=1; else stand=0; for(i=1;i<=3;i++) for(j=1;j<=4;j++) { if(array[i][j]!=stand) { flip(i+1,j); cnt++; } } for(i=1;i<=4;i++) if(array[4][i]!=stand) { printf("Impossible\n"); return 0; } if(cnt==0) { printf("0\n"); return 0; } else { if(cnt<min) min=cnt; for(i=1;i<=4;i++) for(j=1;j<=4;j++) array[i][j]=t[i][j]; } } printf("%d\n",min); return 0; }