题目传送门：http://poj.org/problem?id=3279
题意：
给定长宽的黑白棋棋盘摆满棋子，每次操作可以反转一个位置和其上下左右共五个位置的棋子的颜色，求要使用最少
翻转次数将所有棋子反转为黑色的所需翻转的是哪些棋子与次数。
分析：
首先根据题目，每次操作都会影响到周围的“棋子”，而要使得每个1都被反转为0，那么我们就应当每次都反转1下方
的棋子以改变1为0.那么，当我们处理过1到n-1行的时候，前n-1行就都已经是0了，最后我们只需要检查最后一行是
不是全部为0就可以检查这次的出操作是否正确了。如果正确且最小，那就存起来。最后输出，万事大吉。当然，因
为我们要改变第x行的1为0需要反转的是x+1行的位置。而这个整个规则是我们验证一组操作是否能达到目的所用的，
那么我们需要在验证前先确定操作（没操作怎么验证..）。于是根据规则内容可知，只需要能确认第一行的翻转情况，
就能够推出下面所有的翻转情况并验证是否正确。于是需要做的就是枚举第一行的情况了。
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int maxn = 20; int mp[maxn][maxn], flip[maxn][maxn], best[maxn][maxn]; int dir[5][2] = {0, 0, 0, 1, 0, -1, 1, 0, -1, 0}; int n, m; int get(int x, int y)//判断当前情况下是否需要翻转该点下面的位置 { int now = mp[x][y]; for(int i = 0; i <= 4; i++) { int dx = x + dir[i][0]; int dy = y + dir[i][1]; if(dx >= 0 && dx < n && dy >= 0 && dy < m) { now += flip[dx][dy]; } } return now&1; } int work() { for(int i = 1; i < n; i++) for(int j = 0; j < m; j++) if(get(i-1, j)) flip[i][j]++; for(int i = 0; i < m; i++) if(get(n-1, i)) return 0x3f3f3f3f; int cnt = 0; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cnt += flip[i][j]; return cnt; } int main() { while(cin >> n >> m) { for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> mp[i][j]; int ans = 0x3f3f3f3f, cnt; for(int i = 0; i < (1<<m); i++) { memset(flip, 0, sizeof(flip)); for(int j = 0; j < m; j++) if(1&(i>>j)) flip[0][j]++; int num = work(); if(num < ans) { ans = num; memcpy(best, flip, sizeof(flip)); } } if(ans == 0x3f3f3f3f) cout << "IMPOSSIBLE\n"; else { for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) printf("%d%c", best[i][j], j == m-1 ? '\n':' '); } } return 0; }
