Preface

题目链接

这题真的恶心，状压写错了调半天。。。

Description

给定一个 $4\times 4$ 的棋盘，每一格放一个棋子，共有 $8$ 个黑棋，$8$ 个白棋。每次可以交换相邻两个格子的棋子，问最少要多少步才能从初始状态到达最终状态。并且需要输出交换方法。

Solution

由于棋盘十分小（只有 $4\times 4$ ），所以考虑食用 $bfs$。

这道题主要问题是状态如何考虑。

由于只有黑棋和白棋，所以很自然的就想到了状压的思想。

我们可以考虑将整个棋盘直接状压成一个 $16$ 位二进制数，再进行 $bfs$ 转移。

$2^0$ $2^1$ $2^2$ $2^3$
$2^4$ $2^5$ $2^6$ $2^7$
$2^8$ $2^9$ $2^{10}$ $2^{11}$
$2^{12}$ $2^{13}$ $2^{14}$ $2^{15}$

那么在 $bfs$ 的时候，只需要根据这个状压方法提取出需要交换的两位，并且暴力交换后再压回去即可。

另外，在 $bfs$ 的过程中，记录一下父亲及路径即可，最后递归输出。

Code