poj 1753 Flip Game

牛客题目 poj题目

题目大意：就是说有一个4*4的棋盘，棋盘上有16个黑白棋子随机摆放b代表黑色棋子，w代表白色棋子，现在我们可以操作这个棋盘改变棋子的颜色使整个棋盘最终都只有一种颜色的棋子，操作就是翻转棋子，白色棋子翻转就是黑色，反之亦然，每次翻转一枚棋子，它的周围四个（上、下、左、右）四枚棋子都要随之翻转，求最小翻转次数，使得最终棋盘上只有一种颜色的棋子。

输出：如果当前已经是符合题目的状态那么不用翻转，直接输出0，如果递归之后还是不能变为符合题目的状态那么输出Impossible，否则输出最小翻转次数

方法一：dfs+枚举

这里细讲一下代码里面的两个函数

函数一：change函数

因为题目要求的是翻转本身选中的棋子加上本身的上下左右的棋子，我们可以发现符合这五种情况的坐标都至少含有一个0，他们分别是（0, 0）, （1, 0）,（ 0, 1）, （-1, 0）,（ 0, -1），他们相乘为0，其他相乘为1或者-1

我们也可以改一下change函数，把它改成我们常见的dfs遍历情况，其实是大同小异

void change(int x, int y) { for (int i = -1; i <= 1; ++i) for (int j = -1; j <= 1; ++j) { if (i * j == 1 || i * j == -1) //排除其他方向，保留上下左右 continue; if (x + i >= 1 && x + i <= 4 && y + j >= 1 && y + j <= 4) //判断是不是在范围里面 { //把本身加上上下左右五种情况都翻转 if (c[x + i][y + j] == 'w') c[x + i][y + j] = 'b'; else c[x + i][y + j] = 'w'; } } }

修改后----->常见的dfs遍历方式

int d[5][2] = {0, 0, 1, 0, 0, 1, -1, 0, 0, -1}; void change(int x, int y) { for (int i = 0; i < 5; ++i) { int dx = x + d[i][0]; int dy = y + d[i][1]; if (dx >= 1 && dx <= 4 && dy >= 1 && dy <= 4) { if (c[dx][dy] == 'w') c[dx][dy] = 'b'; else c[dx][dy] = 'w'; } } }

函数二：dfs函数 分析一下里面的剪枝函数，感觉如果自己写的话可能想不到要这么剪枝，确实很巧妙的剪枝，遍历是两层for循环，每次外层循环一次的时候，内层循环都要走一遍所有的情况，所以第一种情况当i<n的时候，我们已经可以不需要去枚举他了，因为即便此时的j>m，我们已经枚举过了，第二种情况，当i==n的时候，如果此时j<m那也不用枚举了。因为也是已经枚举过了，我们每枚举一个点的时候，当前点之前的点都不用枚举了，当时我是这么想的想把剪枝操作改成if(i<=n&&j<=m)这样我们会发现，我们有很多没有必要枚举的枝都没有减去（因为已经枚举过了比如（n-1,m+1）），这样显然会超时

我们用num记录翻转的次数，一旦达到最终状态，那么直接更新

void dfs(int n, int m, int num) { for (int i = 1; i <= 4; ++i) for (int j = 1; j <= 4; ++j) { //已经枚举过的情况就不需要在枚举 if (i < n || (i == n && j <= m)) //剪枝操作 continue; change(i, j); //改变当前点以及上下左右的点的状态 if (judge() && num < ans) //我们要求的是最小翻转数，如果到达最终状态并且翻转次数小于之前的那么就更新一下 { all = 1; ans = num; } dfs(i, j, num + 1); //没有找到继续递归 change(i, j); //递归到最后的时候要重新改回来 } }

AC代码

#include <iostream> #include <algorithm> #include <cstdio> #include <set> #include <map> #include <math.h> #include <vector> #include <queue> #include <string.h> typedef long long ll; using namespace std; #define pi acos(-1.0) const int maxn = 1e5 + 10; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; char c[100][100]; int ans = 1000; void change(int x, int y) { for (int i = -1; i <= 1; ++i) for (int j = -1; j <= 1; ++j) { if (i * j == 1 || i * j == -1) //排除其他方向，保留上下左右 continue; if (x + i >= 1 && x + i <= 4 && y + j >= 1 && y + j <= 4) //判断是不是在范围里面 { //把本身加上上下左右五种情况都翻转 if (c[x + i][y + j] == 'w') c[x + i][y + j] = 'b'; else c[x + i][y + j] = 'w'; } } } int judge() //判断是不是已经符合题目意思的状况 { char a = c[1][1]; for (int i = 1; i <= 4; ++i) for (int j = 1; j <= 4; ++j) if (c[i][j] != a) return 0; return 1; } int all = 0; void dfs(int n, int m, int num) { for (int i = 1; i <= 4; ++i) for (int j = 1; j <= 4; ++j) { //已经枚举过的情况就不需要在枚举 if (i < n || (i == n && j <= m)) //剪枝操作 continue; change(i, j); //改变当前点以及上下左右的点的状态 if (judge() && num < ans) //我们要求的是最小翻转数，如果到达最终状态并且翻转次数小于之前的那么就更新一下 { all = 1; ans = num; } dfs(i, j, num + 1); //没有找到继续递归 change(i, j); //递归到最后的时候要重新改回来 } } int main() { for (int i = 1; i <= 4; ++i) for (int j = 1; j <= 4; ++j) scanf(" %c", &c[i][j]); if (judge()) //如果刚开始就已经是符合题目的状态就输出0 { all = 1; ans = 0; } else dfs(0, 0, 1); //否则递归 if (all) printf("%d\n", ans); else puts("Impossible"); }

方法二：位运算

说实话位运算看起来很头疼

位运算参考链接

#include <iostream> #include <algorithm> #include <cstdio> #include <set> #include <map> #include <math.h> #include <vector> #include <queue> #include <string.h> typedef long long ll; using namespace std; #define pi acos(-1.0) const int maxn = 1e5 + 10; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; using namespace std; const int N = 55; int a[N], b[N]; int x[N], c[N]; int num[N]; int ans = 0x3f3f3f3f; int get_num(int tmp) { int cnt = 0; while (tmp) { if (tmp & 1) ++cnt; tmp >>= 1; } return cnt; } void deal(int a[]) { memset(c, 0, sizeof(c)); for (x[1] = 0; x[1] < 1 << 4; ++x[1]) { int cnt = num[x[1]]; c[1] = a[1] ^ x[1] ^ (x[1] >> 1) ^ ((x[1] << 1) & 15); c[2] = a[2] ^ x[1]; for (int i = 2; i <= 4; ++i) { x[i] = c[i - 1]; cnt += num[x[i]]; c[i] = c[i] ^ x[i] ^ (x[i] >> 1) ^ ((x[i] << 1) & 15); c[i + 1] = a[i + 1] ^ x[i]; } if (!c[4]) ans = min(ans, cnt); } } int main() { for (int i = 0; i < 1 << 4; ++i) num[i] = get_num(i); for (int i = 1; i <= 4; ++i) for (int j = 0; j < 4; ++j) { char s; scanf(" %c", &s); // ' %c'消除回车 if (s == 'b') a[i] |= 1 << j; else b[i] |= 1 << j; } deal(a); deal(b); if (ans == 0x3f3f3f3f) puts("Impossible"); else printf("%d\n", ans); return 0; }

最近看完了柴静写的《看见》，我很喜欢这样说“说真话，做真事的人”

不要因为走的太远，忘记了我们为什么出发。如果哀痛中，我们不再出发 ，那你的离去还有什么意义————陈虻

不要因为走的太远，忘记了我们为什么出发。如果哀痛中，我们不再出发 ，那你的离去还有什么意义 ————陈虻