题目大意
给定大小为4*4的正方形网格，每个网格都有一个棋子（要是正面，要么是反面），要求对棋子进行尽量少的翻转（翻转某个棋子会使得与其有公共边的棋子都翻转），使得所有的棋子全部为正面或者全部为反面
题解
枚举第一行的状态即可，只要第一行确定了，其他每行的操作都确定了
代码写得有点挫。。。。
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> #define MAXN 20 #define INF 0x7fffffff using namespace std; int a[MAXN][MAXN],b[MAXN][MAXN],ans[MAXN][MAXN]; int check1(int s) { int i,j; for(i=0; i<4; i++) if(s&(1<<i)) { ans[0][i]=1; b[0][i]^=1; if(1<4) b[1][i]^=1; if(i-1>=0) b[0][i-1]^=1; if(i+1<4) b[0][i+1]^=1; } for(i=1; i<4; i++) for(j=0; j<4; j++) if(b[i-1][j]) { ans[i][j]=1; b[i][j]^=1; b[i-1][j]^=1; if(i+1<4) b[i+1][j]^=1; if(j-1>=0)b[i][j-1]^=1; if(j+1<4) b[i][j+1]^=1; } for(i=0; i<4; i++) if(b[3][i]) return 0; return 1; } int check2(int s) { int i,j; for(i=0; i<4; i++) if(s&(1<<i)) { ans[0][i]=1; b[0][i]^=1; if(1<4) b[1][i]^=1; if(i-1>=0) b[0][i-1]^=1; if(i+1<4) b[0][i+1]^=1; } for(i=1; i<4; i++) for(j=0; j<4; j++) if(!b[i-1][j]) { ans[i][j]=1; b[i][j]^=1; b[i-1][j]^=1; if(i+1<4) b[i+1][j]^=1; if(j-1>=0)b[i][j-1]^=1; if(j+1<4) b[i][j+1]^=1; } for(i=0; i<4; i++) if(!b[3][i]) return 0; return 1; } int solve() { int i,j,tt=0; for(i=0; i<4; i++) for(j=0; j<4; j++) tt+=ans[i][j]; return tt; } int main(void) { int i,j; char s[10]; while(scanf("%s",s)!=EOF) { for(i=0; i<4; i++) if(s[i]=='b') a[0][i]=1; else a[0][i]=0; for(i=1; i<4; i++) { getchar(); scanf("%s",s); for(j=0; j<4; j++) if(s[j]=='b') a[i][j]=1; else a[i][j]=0; } int mins=INF; for(i=0; i<(1<<4); i++) { memcpy(b,a,sizeof(a)); memset(ans,0,sizeof(ans)); if(check1(i)) mins=min(mins,solve()); } for(i=0; i<(1<<4); i++) { memcpy(b,a,sizeof(a)); memset(ans,0,sizeof(ans)); if(check2(i)) mins=min(mins,solve()); } if(mins==INF) printf("Impossible\n"); else printf("%d\n",mins); } return 0; }