【codevs1004】四子连棋

2016年6月12日4,9800

题目描述 Description

在一个4*4的棋盘上摆放了14颗棋子,其中有7颗白色棋子,7颗黑色棋子,有两个空白地带,任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格,这叫行棋一步,黑白双方交替走棋,任意一方可以先走,如果某个时刻使得任意一种颜色的棋子形成四个一线(包括斜线),这样的状态为目标棋局。

 

输入描述 Input Description

输出描述 Output Description

用最少的步数移动到目标棋局的步数。

样例输入 Sample Input

BWBO
WBWB
BWBW
WBWO

样例输出 Sample Output

5

题解

这显然是一道搜索相关的题目,每次找到空白的格子,将其与四周的棋子进行交换

这类求最小步数的题目往往迭代深搜可以秒杀

如果使用广度搜索,由于总局面数达到4 * 10^7,我们需要对局面进行判重,剪除重复搜索的分枝

这就需要用到哈希表,将局面看做16位的三进制数,转换十进制后取模作为key

 

据说迭代深搜可以秒杀

本题代码不考虑哈希表冲突的情况,不过由于最少步数的情况较多,得到错解的可能性比较低

valid函数用于与空白格交换的格子的合法性

equal用于判断四个字符是否相等

check用于判断是否为最终局面

gethash用于计算局面的哈希值