POJ1753棋盘翻转问题解题报告

也不是突然就开始想写些算法题来着的冲动，只是觉得算法还是相当重要的。在谷歌上搜“算法训练”搜到了一个POJ刷题清单，于是从第一题开始做起。

POJ1753大体题意是：有一个4*4的方格，每个方格中放一粒棋子，这个棋子或白或黑。而规则是每次任选16颗中的一颗，把选中的这颗以及它四周的棋子一并颜色翻转，当所有的棋子都是同一个颜色时，或者说无法通过翻转达到颜色一致的目的，这两种情况都属于游戏完成。现在给定一个初始状态，要求输出能够完成游戏所需翻转的最小次数。特殊情况下，如果初始状态已经达到要求输出0。如果不可能完成游戏，输出Impossible。

解题思路：

1. 当我们使用0或者1两种状态来表示棋子的黑色或者白色时，方格就可以被转化成一个16位的二进制状态数。而游戏完成正好对应这个数为0或者65535的状态，于是我们就可以通过对这个16位二进制状态数的数值来判断游戏是否结束。

2. 棋子及其四周棋子的翻转需要考虑的是对于边界棋子情况的分析。棋子的翻转可以通过异或操作实现。

3. 本题主要运用的思想还有BFS广度优先搜索算法，通过一个数组（包含rear和front）记录搜索过程中记到的所有情况，以此在这些情况上进行翻转变换，并把新产生的棋盘局面不断记录到队首，以此实现对棋盘的所有情况的枚举。枚举过程中需要注意的一点是想办法防止重复的枚举，不然程序可能就会进入死循环状态，我这里是开了一个数组visit对是否访问进行标记。

---

原题链接：POJ1753

附本人AC代码：

#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;

int state=0;//用来记录当前棋盘值
int rear=0,front=0;//记录队列的头和尾
bool visit[65540];//用来标记状态访问程度
int states[65536];//记录搜集的状态
int steps[65540];//用来记录steps

int exclusive_or(int i)//翻转函数
{
	state = states[front-1];
	state ^= 1<<i;
	if (i%4!=0) state ^= 1<<(i-1);
	if (i%4!=3) state ^= 1<<(i+1);
	if (i+4<16) state ^= 1<<(i+4);
	if (i-4>=0) state ^= 1<<(i-4);
	return state;
}

int bfs()
{
	while (rear > front)
	{
		state = states[front++];
		if (state == 0 || state == 65535)//一旦找到，立即返回
			return steps[state];
		for (int i = 0; i < 16; i++)
		{
			int count=exclusive_or(i);
			if (visit[count] == false)
			{
				states[rear++]=count;
				visit[count]=true;
				steps[count]=steps[states[front-1]]+1;
			}
		}
	}
	return -1;
}

int main()
{
	int ans;
	char temp[5];
	memset( visit, false, sizeof(visit));//初始化
	memset( steps, 0, sizeof(steps));
	memset( states, 0, sizeof(states));

	for (int i= 0; i < 4; i++)
	{
		scanf("%s",temp);
		for (int j = 0; j < 4; j++)
		{
			state<<=1;
			if (temp[j] == 'w') state = state | 0;
			else state = state | 1;
		}
	}
	states[rear++]=state;
	visit[state]=true;

	ans = bfs();//bfs宽度遍历，搜索每种状态，并返回steps或者-1
	if (ans == -1) printf("Impossible\n");
	else printf("%d\n", ans);
	//system("pause");
	return 0;
}

另解：

当然，在小型棋盘中这样处理都不是问题。但如果棋盘范围扩大十倍呢？这是P东提供给我的另一种思路，显然在问题改变的情况下，我的思路已经不是最优的了，下面就来介绍一下P东的想法。

由于棋盘上棋子翻转的任意性，如果不能有一个好的处理流程，一定会被烦得手忙脚乱。但需要注意的一点是，如果我们按照从上往下搜索的思路来进行，那么每一行的棋子翻转只会影响到上一行的棋子颜色。所以这样就催生了更好的解法：

枚举第一行状态，之后从第二行开始所有需要翻转的棋子都确定了（为了让上一行为一个颜色）。做一遍黑的 做一遍白的 OK了。比搜索的复杂度低很多。

举个例子就是：假设现在棋盘的布局第一行为黑白黑黑，那么我们首先要做的就是把第一行棋子变换所能产生的所有情况遍历出来，然后对每个情况执行如下处理（以下以“黑白黑黑”情况处理）：

第二行为了让第一行全黑（或者全白）必须翻转其中第二个棋子，其余不动；而第三行为了让第二行全为黑 又必须翻转相应的棋子；最后一行同理，此时如果棋盘全为黑，找到一个可行解。最后用所有可行解对比找一个次数最少的就可以找到最优解。

是不是很妙？

---

感谢coding过程中李松提供的帮助与指导。感谢好机油P东提供的解题新思路。