【BHOJ ModricWang的星灵棋】状压 | BFS | STL | 棋类 | trick : [0]数组 | N
ModricWang的星灵棋
核心：状压 + BFS （后面还有一个小trick补充 + 小彩蛋哦）
时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 130 总提交人数: 156
题目简述
星灵棋规则如下：在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白格，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步。黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局，先达到目标棋局者赢。
给定当前的棋局状态，请你帮ModricWang算出最少还要多少步才能下完这盘棋。
输入
只有一组数据。
输入4*4的初始棋局，黑棋子用B表示，白棋子用W表示，空格用O表示。
保证输入格式严格符合规范，总共只有4个连续的可见行，每行只有4个连续的可见字符。不存在前导空行或前导空格。
保证输入数据完全符合规则，总共有7个B，7个W和2个O。
输出
用最少的步数移动到目标棋局的步数。
输入样例
BWBO
WBWB
BWBW
WBWO输出样例
5分析
这道题跟八数码有点像，移动方式是一样的，题目类型也是一样的，所以主要算法仍然是BFS。
不同的是状态的表示和目标局面的情况。由于这道题是棋子类型，所以状态的表示不能用康托展开，而可以用状态压缩。如果黑棋是0x1，白棋是0x2，空格是0x0，那么整个棋局（16个棋子）就可以用一个 unsigned int 表示。相应地，记录访问的数据结构也不能用普通数组了（会爆），而可以选用 std::unordered_set<unsigned int> 来做访问记录。
一、设计BFS：如何存储状态、如何扩展状态
为了更快地记录棋型以及判断胜负，这里采用了一种比较特殊的棋盘存储方式。也就是说棋盘存储有四部分：
- uchar row[4] ，每个 uchar 代表一行（8bit，四个子）
- uchar col[4] ，每个 uchar 代表一列（8bit，四个子）
- uchar left ，代表左对角线（8bit，四个子）
- uchar right ，代表右对角线（8bit，四个子）
这样的话，只用把这十个 unsigned char 和 0x55（四连黑棋） 以及 0xaa（四连白棋）做按位与，就可以判断是否达到胜利局面了（当然也可以开一个bool下标映射数组，只有当下标是 0x55 或 0xaa 的时候才是 true）
但是这样做的代价是每一次移动棋子的时候需要修改其所在行、列的对应的两个bit，并且如果在对角线上的话还需要更新对角线的对应的两个bit。
因此要写这么两个函数：
// 修改 r 行 c 列的棋子为 p
inline bool putChess(const int r, const int c, uchar p)
{
uchar pl2r = p << 2*r, pl2c = p << 2*c,
al2r = ~(3 << 2*r), al2c = ~(3 << 2*c);
row[r] &= al2c, row[r] |= pl2c;
if (WIN[row[r]]) return true; // 移动后产生必胜棋型，直接返回
col[c] &= al2r, col[c] |= pl2r;
if (WIN[col[c]]) return true; // 移动后产生必胜棋型，直接返回
if (r == c) // 在左对角线上
{
left &= al2c, left |= pl2c;
if (WIN[left]) return true; // 移动后产生必胜棋型，直接返回
}
if (r+c == 3) // 在右对角线上
{
right &= al2r, right |= pl2r;
if (WIN[right]) return true; // 移动后产生必胜棋型，直接返回
}
return false; // 移动后没有产生必胜棋型
}
// 获取 r 行 c 列的棋子
inline uchar getChess(const int r, const int c) const
{
return (row[r] >> 2*c) & 3;
}这样的话，棋盘存储和移动和胜利判断就ok了。
同时，BFS的状态扩展也可以很方便地完成（直接调用函数修改某行某列的棋子，实现空白格的移动）
那么状态struct就可以设计成：
- 棋盘（row[4]、col[4]、left、right）
- 两个空格的位置（记录空格所在行列）（便于去扩展状态）
- 当前行动的玩家（便于正确地扩展状态）
二、如何通过状态获取对应的哈希值（用于做访问标记）
那么要怎么获取当前棋盘对应的那一个唯一的 unsigned int 呢（为了做 visited 标记）？
容易想到的办法是二重循环遍历棋盘 + 不断的移位和按位或，不过这样做实在是太傻。
比较聪明的办法是直接利用row数组，通过 ((unsigned int)row[0] << 24) | ((unsigned int)row[1] << 16) | ((unsigned int)row[2] << 8) | ((unsigned int)row[3]) 来获取。
有一个更好的办法是 *(unsigned int*)(row) 直接获取。通常来说这样就可以了，就是不怎么优雅。
但是我还有一个更好的办法，也就是在结构体里面放一个 unsigned int “指针”。肯定有人有疑问了，这样的话指针还要初始化，并且还占用了额外的 32 个字节，不划算啊。但是我这个 “指针” 其实并不是普通意义上的指针，它是长这样的：
struct State
{
unsigned int uintValue[0];
uchar row[4], col[4];
uchar left, right;
... ... 这个 uintValue，它可以一次性读它后面的 32 个bit ，直接当指针使，还不会浪费一点空间。用这个方式，既保持了代码的优雅，又保证了效率。（关于这个[0]数组的trick，文末还有详细介绍：* Trick ：结构体中的 [0] 数组）
这样的话，整个BFS的思路就ok了。接下来上代码。
AC代码
#include <cstdio>
#include <cstring>
#include <unordered_set>
enum
{
BLACK_CHESS = 1,
BLACK_TURN = 1,
WHITE_CHESS = 2,
WHITE_TURN = 2,
NO_CHESS = 0
};
typedef unsigned char uchar;
std::unordered_set<unsigned int> _[5], *VIS=_+2;
bool WIN[0xaa+1];
struct State
{
unsigned int uintValue[0];
uchar row[4], col[4];
uchar left, right;
uchar r1, c1;
uchar r2, c2;
short step, turn;
State(void) : step(0), turn(BLACK_TURN) { }
inline bool putChess(const int r, const int c, uchar p)
{
uchar pl2r = p << 2*r, pl2c = p << 2*c,
al2r = ~(3 << 2*r), al2c = ~(3 << 2*c);
row[r] &= al2c, row[r] |= pl2c;
if (WIN[row[r]]) return true;
col[c] &= al2r, col[c] |= pl2r;
if (WIN[col[c]]) return true;
if (r == c)
{
left &= al2c, left |= pl2c;
if (WIN[left]) return true;
}
if (r+c == 3)
{
right &= al2r, right |= pl2r;
if (WIN[right]) return true;
}
return false;
}
inline uchar getChess(const int r, const int c) const
{
return (row[r] >> 2*c) & 3;
}
};
State queue[666666];
#define RET return printf("%d", queue[tail].step), 0
#define UPDATE(r1, c1) \
if (now.r1>0 && now.getChess(now.r1-1, now.c1) == now.turn) \
{ \
queue[tail] = now; \
--queue[tail].r1, ++queue[tail].step; \
if (queue[tail].putChess(queue[tail].r1, now.c1, NO_CHESS)) RET; \
if (queue[tail].putChess(now.r1, now.c1, now.turn)) RET; \
if (!VIS[now.turn-1].count(*queue[tail].uintValue)) \
{ \
VIS[now.turn-1].insert(*queue[tail].uintValue); \
queue[tail++].turn = 3-now.turn; \
} \
} \
if (now.c1>0 && now.getChess(now.r1, now.c1-1) == now.turn) \
{ \
queue[tail] = now; \
--queue[tail].c1, ++queue[tail].step; \
if (queue[tail].putChess(now.r1, queue[tail].c1, NO_CHESS)) RET; \
if (queue[tail].putChess(now.r1, now.c1, now.turn)) RET; \
if (!VIS[now.turn-1].count(*queue[tail].uintValue)) \
{ \
VIS[now.turn-1].insert(*queue[tail].uintValue); \
queue[tail++].turn = 3-now.turn; \
} \
} \
if (now.r1<3 && now.getChess(now.r1+1, now.c1) == now.turn) \
{ \
queue[tail] = now; \
++queue[tail].r1, ++queue[tail].step; \
if (queue[tail].putChess(queue[tail].r1, now.c1, NO_CHESS)) RET; \
if (queue[tail].putChess(now.r1, now.c1, now.turn)) RET; \
if (!VIS[now.turn-1].count(*queue[tail].uintValue)) \
{ \
VIS[now.turn-1].insert(*queue[tail].uintValue); \
queue[tail++].turn = 3-now.turn; \
} \
} \
if (now.c1<3 && now.getChess(now.r1, now.c1+1) == now.turn) \
{ \
queue[tail] = now; \
++queue[tail].c1, ++queue[tail].step; \
if (queue[tail].putChess(now.r1, queue[tail].c1, NO_CHESS)) RET; \
if (queue[tail].putChess(now.r1, now.c1, now.turn)) RET; \
if (!VIS[now.turn-1].count(*queue[tail].uintValue)) \
{ \
VIS[now.turn-1].insert(*queue[tail].uintValue); \
queue[tail++].turn = 3-now.turn; \
} \
}
bool BFS(const State &src)
{
int head = 0, tail = 2;
queue[0] = queue[1] = src;
queue[1].turn = WHITE_TURN;
VIS[BLACK_TURN-1].insert(*src.uintValue); // 黑子先行的VIS
VIS[WHITE_TURN-1].insert(*src.uintValue); // 白子先行的VIS
while (head != tail)
{
const State &now = queue[head++];
UPDATE(r1, c1);
UPDATE(r2, c2);
}
}
int main()
{
State src;
memset(&src, 0, sizeof src);
WIN[0xaa] = WIN[0x55] = true; // 这样就可以更快地判断是否获胜
for (int r=0, first_zero=1; r<4; ++r)
{
char str[123];
scanf("%s", str);
for (int c=0; c<4; ++c)
{
switch(str[c])
{
case 'B':
if (src.putChess(r, c, BLACK_CHESS))
return puts("0"),0;
break;
case 'W':
if (src.putChess(r, c, WHITE_CHESS))
return puts("0"),0;
break;
case 'O': // 记录最开始的两个空格位置
if (first_zero)
src.r2 = r, src.c2 = c, first_zero = 0;
else
src.r1 = r, src.c1 = c;
break;
}
}
}
BFS(src);
}最后补充一下关于这个[0]数组的小trick：
* Trick ：结构体中的 [0] 数组
关于这种[0]数组，除了在本题中当一个不占空间的指针使，还有一个更大的作用就是实现柔性数组。
关于柔性数组详细的说明大家可以看这篇博客，讲得很清楚：深入浅出C语言中的柔性数组
最后是小彩蛋啦~
其实这道题的这种状压方式是源自我的一个五子棋算法项目：Ke-Coding/Gobang_by_Kevin-by-Qt-
欢迎大家去试试哦~