题目链接：点击打开链接 题意： 给出m行、n列的棋盘，每一个格子只有两种状态0或1，每次可以选择一个格子执行翻转操作，并且与该格子相邻的4个格子都会被翻转，求将所有格子都翻转成0所需要的最小操作方案，若有多种翻转方法，输出字典序最小的方案。 思路： 看到题目首先想到的为搜索，这题和之前做的求棋盘翻转到目标状态需要的最小次数的题很类似，可是这题让给出具体的翻转序列，这样就不能根据广搜只考虑状态变化了，也许可以想到暴力枚举翻转情况，可是怎么加入搜索的思想呢？难道要枚举整个棋盘所有的翻转情况吗？其实没有必要，因为最后要求的状态是棋盘全0，那么第一行也一定是零，所以先枚举第一行的翻转情况，然后根据第一行的情况，去计算第二行翻转序列的取值，这样类似的去逐行处理，直到最后一行，肯定是可以的。注意的是，翻转矩阵/序列没有先后次序，只要翻转矩阵/序列确定，无论翻的次序如何，最后结果不变，比如在处理一行时，一个位置，左右中上的随意组合标记了翻转，那么直接根据翻转的次数和原图信息决定下一行该位置状态即可，不用理会谁先处理。 具体是，处理到某行某列，根据原图该位置信息和翻转矩阵左右上中对该位置的影响，决定下一行翻转矩阵该列的取值。
// POJ 3279 Fliptile.cpp 运行/限制：563ms/2000ms #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; #define INF 0X3f3f3f3f int m, n; int map[20][20], temp[20][20], re[20][20]; int next[4][2] = { {0,1},{0,-1},{0,0}, {-1,0} };//左右中上 bool check(int row, int loc) { int t = map[row][loc]; for (int i = 0; i < 4; i++) {//原图 与 翻转矩阵的该位置 在左右中上的状态 相异或，得翻转矩阵该位置下方为 1 还是 0 for (int i = 0; i < 4; i++) { int x = row + ::next[i][0]; int y = loc + ::next[i][1]; if (x >= 0 && x < m && y >= 0 && y < n) { t ^= temp[x][y]; } } } return t; } int dfs(int row) { if (row == m - 1) {//最后一行 for (int i = 0; i < n; i++) { if (check(m - 1, i)) {//当最后一行要求翻转矩阵下一行同位置处为1，满足不了 return -1; } } int sum = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { sum += temp[i][j]; } } return sum; } for (int i = 0; i < n; i++) { if (check(row,i)) { temp[row + 1][i] = 1; } } return dfs(row + 1); } void solve() { int sum = INF,upper = 1 << n; for (int i = 0; i < upper; i++) {//枚举第一行的翻转情况 int num = i; memset(temp, 0, sizeof(temp)); for (int j = n - 1; j >= 0; j--) {//生成第一行的翻转序列 temp[0][j] = num & 1; num >>= 1; } int te = dfs(0); if (te != -1 && te < sum) { sum = te; memcpy(re, temp, sizeof(temp)); } } if (sum == INF) { printf("IMPOSSIBLE\n");//IMPOSSIBLE } else{ for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { printf("%d%c", re[i][j], j == n - 1 ? '\n' : ' '); } } } } int main(){ while (scanf("%d%d", &m, &n) != EOF) { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { scanf("%d", &map[i][j]); } } solve(); } return 0; }
