#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>
#include <map>
#include <set>
using namespace std;
const int maxn = 4;
//可移动方向
int dir[4][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
struct Status {
//last = 1 : 黑子, last = 2 : 白子
//包括把16位3进制转换成一个十进制数的结果hash,移动步数step
int hash, step, last; //hash:为了描述棋子的位置信息,但是不能重复
int map[maxn][maxn];
} Map;
/*
* h[1][x]记录黑子放的移动到达的信息
* h[1][x]=false，表示还没有移动这个状态
* h[1][x]=true, 表示之前已经到达过, 不用进队
*/
map<int, bool> h[3];
queue<Status> que; //BFS, 队列
void input(); //输入数据
void solve(); //启动函数
bool judge(int r, int c); //判断越界
bool check(Status a); //判断是否满足目标状态
//移动一步，生成新的棋子位置, k 为移动方向
void Move(Status now, int r, int c, int k);
void findSpace(const Status& now, int &r, int &c, int &r2, int &c2); //找到空格的位置
//把此时棋盘的状态, 全部用0,1,2表示每一位的三进制,转换成一个十进制
int getHash(Status a); //对当前棋盘的棋子设置HashCode
void BFS(); //宽搜BFS
void input()
{
char s[10];
/*
* 把每一位的棋子 换成 空格-0,黑子-1, 白子-2 (三进制)
* 这是一个16位的3进制数, 对应一个十进制数, 然后通过哈希该
* 棋盘的十进制数, 则可找到对应的棋盘状态
*/
for (int i = 0; i < maxn; i++)
{
scanf("%s", s);
for (int j = 0; j < maxn; j++) {
if (s[j] == 'B') Map.map[i][j] = 1;
if (s[j] == 'W') Map.map[i][j] = 2;
}
}
}
bool judge(int r, int c)
{
return (r >= 0 && r < maxn) && (c >= 0 && c < maxn);
}
bool check(Status a)
{
bool flag = true;
//横向连成4个
for (int i = 0; i < maxn; i++)
{
flag = true;
for (int j = 0; j < maxn - 1; j++) {
if (a.map[i][j] != a.map[i][j + 1]) {
flag = false;
}
}
if (flag) return true;
}
//纵向连成4个
for (int i = 0; i < maxn; i++)
{
flag = true;
for (int j = 0; j < maxn - 1; j++) {
if (a.map[j][i] != a.map[j + 1][i]) {
flag = false;
}
}
if (flag) return true;
}
flag = true;
for (int i = 0; i < maxn - 1; i++) {
if (a.map[i][i] != a.map[i + 1][i + 1]) {
flag = false;
}
}
if (flag) return true;
flag = true;
for (int i = maxn - 1; i > 0; i--) {
if (a.map[i][i] != a.map[i - 1][i - 1]) {
flag = false;
}
}
if (flag) return true;
//都没有连成4子, false
return false;
}
//全部用0,1,2表示每一位的三进制,转换成一个十进制
//用了Hash查找
int getHash(Status a)
{
int res = 0;
int k = 1;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
res += a.map[i][j] * k;
k *= 3;
}
}
return res;
}
void findSpace(const Status& now, int &r1, int &c1, int &r2, int &c2)
{
for (int i = 0; i < maxn; i++)
{
for (int j = 0; j < maxn; j++) {
if (!now.map[i][j])
{
if (r1 == -1 && c1 == -1) {
r1 = i; c1 = j;
}
else {
r2 = i; c2 = j;
}
}
}
}
}
/*每移动 一步,都需要对其进行
* 1.是否越界检查
* 2.移动棋子, 并标志移动, 并设置下一次移动的棋子种类
* 3.是否完成目标检查
* 4.未完成 则 设置新棋盘的HashCode
* 5.检查该棋子状态 是否出现过, 没有则入队，并标志为出现过
*移动一步，生成新的棋子位置, k 为移动方向
*/
void Move(Status now, int r, int c, int k)
{
Status tmp = now;
int tmpx = r + dir[k][0];
int tmpy = c + dir[k][1];
//判断是否越界 || 先后手, 不能两次都移动自己的子
//(如,第一次移动白子,第二次,白子能够移动还移动白子,是错误行为
if (!judge(tmpx, tmpy) || tmp.map[tmpx][tmpy] == tmp.last)
return;
tmp.last = 3 - tmp.last; //取反,上次白子(1), 这次就黑子(2)
swap(tmp.map[tmpx][tmpy], tmp.map[r][c]); //交换棋子和空白位置
tmp.hash = getHash(tmp); //重新设置hashCode
tmp.step++; //移动成功,步数+1
if (check(tmp)) {
printf("%d
", tmp.step);
exit(0); //结束整个程序
}
//表示tmp.last这个种类, 单独的某个棋子 当前的状态-是否移动过
//false-没有移动过，可以入队
if (!h[tmp.last][tmp.hash])
{
h[tmp.last][tmp.hash] = true; //标志此状态已经出现过
que.push(tmp); //入队
}
}
void BFS()
{
Map.hash = getHash(Map); //首状态棋盘对应的HashCode
//因为谁先下都行，所以两个棋子都应该入队
Map.last = 1;
que.push(Map);
Map.last = 2; //黑
que.push(Map);
while (!que.empty())
{
Status now;
now = que.front();
que.pop();
int r1 = -1, c1 = -1, r2 = -1, c2 = -1;
findSpace(now, r1, c1, r2, c2); //找到空格位置
//一个棋盘有两个空格,所以两个一起来搜索四个方向
for (int k = 0; k < maxn; k++) {
Move(now, r1, c1, k);
Move(now, r2, c2, k);
}
}
}
void solve()
{
input();
BFS();
}
int main()
{
solve();
return 0;
}
BFS算法不错的练习~
参考了这篇博客: http://blog.csdn.net/re_cover/article/details/9034219