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完成判重