POJ1753 Flip Game
题意简述：
$4×4$ 的棋盘，只有黑白两种颜色的方块，翻动一个棋子后，其周围四个方块也会翻动（四连通）。现给定一个初始状态，求到达全黑或全白的最少翻动次数
分析：
棋盘 $4×4$ ,可以暴力枚举+状态压缩，强行枚举每翻转一次的状态，暴力宽搜求解。总共 $2^{16}(=65536)$ 种情况,每次要考虑 $16$ 种可能性，总的复杂度为 $O( 2^{4^2} * 4^2 )$ ，也就是 $O(2^{n^2} * n^2)$ ，当 $n$ 取 $4$ 时，完全可以考虑。
其实还有其他两种写法，效率都比较高：
但是我都不会写
- 枚举第一排所有情况向后层递推；
- 将图论转化为数论，利用棋盘上每一点的数学关系（翻转次数的奇偶）建立方程组，高斯消元求解
代码实现
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>
using namespace std;
int s;
queue <int> q;
int d[(1<<16) + 10];//用来记步数
int main()
{
char c;
for (int i = 1; i <= 16; i++ )
{
cin >> c;
if(c == 'b') s = (s << 1) + 1;
else s = (s << 1) + 0;
}
q.push(s);
while(!q.empty())
{
int Old = q.front();q.pop();
int New = Old;
if (New == 0 || New == ((1 << 16) - 1))//全黑或全白返回（全为0或1）
{
cout << d[New] <<endl;
return 0;
}
// 1 << i 代表第i个点为黑点 ，
//同时利用 0,1 与 1 异或 改变符号的方法模拟翻转
for (int j = 0; j <= 15; j++)
{
New = Old;
New = New ^ (1 << j);//翻转第j点
if(j > 3)//不在第一排
New = New ^ (1 << (j - 4));//可以翻转前一排的点
if(j < 12)//不在最后一排
New = New ^ (1 << (j + 4));//可以翻转后一排的点
if(j%4 != 0)//不在第一列
New = New ^ (1 << (j - 1));//可以翻转前一列的点
if(j%4 != 3) //不在最后一列
New = New ^ (1 << (j + 1));//可以翻转后一列的点
if(d[New] == 0)//未经过
{
d[New] = d[Old] + 1;//步数加一
q.push(New);
}
}
}
cout << "Impossible" <<endl;
return 0;
}
