1004 四子连棋
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题解
题目描述 Description
在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。
●
○
输入描述 Input Description
输出描述 Output Description
用最少的步数移动到目标棋局的步数。
样例输入 Sample Input
BWBO
WBWB
BWBW
WBWO
样例输出 Sample Output
5
这个题范围特别小，但很麻烦。
需要考虑的东西：下次该哪个棋子走，移动哪个空白格，如何判断状态是否符合要求，如何判重
这些问题需要一步步解决，首先我用结构体存储整个棋盘，包括棋盘里的棋子排布，下一次不该哪种棋子走（也可以认为这种局面是由哪种棋子走来而造成的）
搜索的进行两次，一次是第一步黑子先出，另一次是第一步白子先出。
接下来一些普通的bfs步骤
判重用的是hash，把整个棋盘转化为由0,1,2构成的字符串，借助map完成判重