filp game （枚举法，DFS深搜，位运算，高斯消元）详解 bolg:moonl1ght.xyz
2018年8月4日
题目来源：ZOJ2025 或 POJ1753
题目大意：给定一个 4 × 4 的棋盘，每个位置给了放好棋子，棋子有两个面，按规则进行翻转，使所有棋子都是同一个面。
解题思路：第一次接触到这种题目，刚开始是一点思路都是没有的，这是实话。翻阅网上的题解，发现这一题最长出现的标签是枚举，和深搜，那么我们不妨从枚举与深搜这个角度去看着一题目（该题还有其他解法）
枚举：即列举出所有的可能性，然后进行判断，输出符号题目条件的，那么这一题该怎么枚举呢，这是一个4 × 4的棋盘，那么棋盘大小我们是很确定的知道的，很明显这个 4 × 4 必然与枚举的范围是有关的，因为是翻转棋子，所以每个棋子只有两种情况就是 翻 或者 不翻
2（第一个棋子两种可能） * 2（第二个棋子两种可能） * 2（第三个棋子两种可能）* … … * 2（第16个棋子两种可能）
那么总的可能数就得216，只需要枚举出所有的可能数就好了
（有人直接用for循环写，是真的刚）
那么就要开始于dfs结合（可以参考下dfs的模板，如果不太会写的话）
void dfs()//参数用来表示状态
{
if(到达终点状态)
{
...//根据题意添加
return;
}
if(越界或者是不合法状态)
return;
if(特殊状态)//剪枝
return ;
for(扩展方式)
{
if(扩展方式所达到状态合法)
{
修改操作;//根据题意来添加
标记；
dfs（）；
(还原标记)；
//是否还原标记根据题意
//如果加上（还原标记）就是 回溯法
}
}
} 我们的终点状态很容易知道就是一个棋子都不翻，但16个棋子已经是同一个面了
棋盘有大小限制，所以越界状态也很容易清楚了，代码如下
bool dfs(int n, int i, int j){
//翻 n 个棋子，棋子的坐标为 i 行， j 列
if(n == 0)
{
return check();//判断是否符合条件
}
//从翻16个棋子开始逐一减少
//一个棋子都不用翻
j += 1; //下一列每次搜下一列，如果不加的话会超时，就是dfs出不去
//越界情况
if(j > 4){
i += 1;
j = 1;
}
if(i > 4){
return false;
}
//如果超过棋盘大小则重置
for(; i <= 4; i++){
for(; j <= 4; j++){
flip(i,j);//翻转
if( dfs(n-1, i, j)){
return true;//如果符合条件就直接返回true这个值了
}
//不符合条件那再翻转回去
flip(i,j);//翻转
}
j = 1;
}
return false;
}Q:如何处理输入的字符棋盘呢？
A：化简成数字 0 与 1，由于棋子只存在两种状态 0 态 与 1 态，异或便成为了一个很好地选择
关于异或的介绍
按位或运算符
按位或运算将两个运算分量的对应位按位遵照以下规则进行计算：
0 | 0 = 0, 0 | 1 = 1, 1 | 0 = 1, 1 | 1 = 1
即只要有1个是1的位，结果为1，否则为0。
注意：只比较最后一位，所以可以省略很多步骤
按位异或运算符(^)
按位异或运算将两个运算分量的对应位按位遵照以下规则进行计算：
0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0
即相应位的值相同的，结果为 0，不相同的结果为 1。
这个则是每个位置都比较
接下来就是翻转部分的函数，每次我翻转（i， j）位置的棋子， 上下左右（需在范围内）的棋子都要发生翻转
不妨将每一行都看作是一个数（16进制数），因为16进制数每四位是一位数，刚好与棋盘大小相符合，例如 一行棋子1 0 0 1 如果要对第二位进行翻转的话就要用0 1 0 0（16进制）就是 8，那么我们很容易得到帮助翻转的状态数
int state[][4] ={ {8, 4, 2, 1},{12, 14, 7, 3}}; // 1000 , 0100, 0010, 0001//翻转函数
void flip(int i, int j){
--j;
//对(i, j)位置的棋子进行翻转
CheckerBoard[i-1] ^= state[0][j];
CheckerBoard[i+1] ^= state[0][j];
CheckerBoard[i] ^= state[1][j];
}判断函数，就是每行16进制数都等于0或者15（因为1111是15的16进制数）
bool check(){
/*
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
8+4+2+1 == 15
*/
return ((CheckerBoard[1] == 0 || CheckerBoard[4] == 15) && CheckerBoard[1] == CheckerBoard[2] && CheckerBoard[2] == CheckerBoard[3] && CheckerBoard[3] == CheckerBoard[4]);
}//ac代码poj是无法用万能头文件的，会ce
#include <iostream>
#include <algorithm>
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REP_(i, a, b) for(int i = a; i <= b; i++)
#define sl(n) scanf("%lld", &n);
#define si(n) scanf("%d", &n);
#define RepAll(a) for(auto x: a)
#define cout(ans) cout << ans << endl;
typedef long long ll;
//位运算的解法
using namespace std;
int CheckerBoard[8];
void read(){
REP_(i, 1, 4){
REP_(j, 1, 4){
//cout << "after change :" << CheckerBoard[i] << '\n';
CheckerBoard[i] <<= 1;
//cout << "now :" << CheckerBoard[i] << '\n';
if(getchar() == 'b'){
CheckerBoard[i] |= 1; //与1相或,于是就只改变最后一位
}
} getchar();//读取换行符号
}
return;
}
//每一行压缩一个数字，对第 i 行第 j 列棋子进行翻转，
//比如j = 2 j = 2，则(i−1 、 i+1)行的棋子应该和4（0100）相异或（与1异或切换状态，与0异或不改变）
//，而第 i 行棋子应与14（1110）相异或。
int state[][4] ={ {8, 4, 2, 1},{12, 14, 7, 3}};//1000, 0100, 0010, 0001,
void flip(int i, int j){
--j;
//对(i, j)位置的棋子进行翻转
CheckerBoard[i-1] ^= state[0][j];
CheckerBoard[i+1] ^= state[0][j];
CheckerBoard[i] ^= state[1][j];
}
bool check(){
/*
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
8+4+2+1 == 15
*/
return ((CheckerBoard[1] == 0 || CheckerBoard[4] == 15) && CheckerBoard[1] == CheckerBoard[2] && CheckerBoard[2] == CheckerBoard[3] && CheckerBoard[3] == CheckerBoard[4]);
}
bool dfs(int n, int i, int j){
//翻 n 个棋子
if(n == 0)
{
return check();//判断是否符合条件
}
//从翻16个棋子开始逐一减少
//一个棋子都不用翻
j += 1; //下一列, 如果不加则会超时
if(j > 4){
i += 1;
j = 1;
}
if(i > 4){
return false;
}
//如果超过棋盘大小则重置
for(; i <= 4; i++){
for(; j <= 4; j++){
flip(i,j);//翻转
if( dfs(n-1, i, j)){
return true;
}
flip(i,j);//翻转
}
j = 1;
}
return false;
}
void slove(){
for(int i = 0; i <= 16; i++){
if(dfs(i, 1, 0)){
cout << i << '\n';
return ;
}
}
cout << "Impossible" << '\n';
}
int main(){
read();
slove();
return 0;
}
京公网安备 11010502036488号