题目链接：http://poj.org/problem?id=3279 题意：有一个n*m的棋盘，上面 摆满了棋子，有的是白棋，有的是黑棋，问你能否通过翻转把他变成全为白色的棋子，翻转一个棋子，周围的棋子都变成相反的颜色，如果能则输出一个相应的矩阵，只不过每一位表示翻转的次数，总翻转次数要最少，如果不能就输出impossible 解析：如果是自己来玩这个游戏的话，肯定是，如果上一行是黑色的，那么我一定会翻下面的那个棋子，那么第一行如何翻，就能决定第二行怎么翻了，同理，就可以决定接下来的所有行怎么翻了，所以我们只需要枚举第一行的所有状态即可
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int inf = 0x7fffffff; int a[15][15]; int ans[15][15]; int tmp[15][15]; int n,m; int dx[] = {0,-1,1,0,0}; int dy[] = {1,0,0,-1,0}; int getv(int x,int y) { int res = a[x][y]; for(int i=0;i<5;i++) { int tx = x+dx[i]; int ty = y+dy[i]; if(tx<0 || tx>=n ||ty<0 || ty>=m) continue; res += tmp[tx][ty]; } return res&1; } int work() { for(int i=1;i<n;i++) { for(int j=0;j<m;j++) { if(getv(i-1,j)) tmp[i][j] = 1; } } for(int i=0;i<m;i++) { if(getv(n-1,i)) return inf; } int res = 0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) res += tmp[i][j]; } return res; } int main(void) { while(~scanf("%d %d",&n,&m)) { for(int i=0;i<n;i++) { for(int j=0;j<m;j++) scanf("%d",&a[i][j]); } memset(ans,0,sizeof(ans)); int res = inf; for(int i=0;i<1<<m;i++) { memset(tmp,0,sizeof(tmp)); for(int j=0;j<m;j++) tmp[0][j] = i>>j&1; int tt = work(); if(tt<res) { res = tt; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) ans[i][j] = tmp[i][j]; } } } if(res==inf) { puts("IMPOSSIBLE"); continue; } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(j)printf(" "); printf("%d",ans[i][j]); } puts(""); } } return 0; }