問題描述 Description

有這樣一種有趣的棋類游戲，假設有一個N×N$N/times N$方格的棋盤，棋盤中存在障礙格，即該格子不能放置棋子。棋盤上有若干個白色棋子和黑色棋子隨機擺放，每個格子只能放一個棋子。現在你知道棋盤的初始狀態和最終狀態，請問最少需要移動幾次棋子才能從初始狀態達到最終狀態。棋子的移動規則如下: 1. 每次選擇1枚棋子進行移動。 2. 必須先移動白棋，按照先白棋后黑棋的順序交替進行。 3. 每次選擇的棋子可以在水平、垂直以及對角線共計8個方向中的任意方向上移動，棋子每次移動只有當遇到棋盤邊界，棋盤中的障礙或者其他的棋子時才會停止。 4. 棋盤中的障礙格不能移動。

輸入 Input

第一行給出N$N$。 接下來輸入包括2×N$2/times N$行，每行N$N$個字符。前N$N$行表示棋盤的初始狀態，后N$N$行表示棋盤的最終狀態。 字符w表示白色棋子，字符b表示黑色棋子，字符#表示棋盤中的障礙，字符*表示棋盤中的空格。保證黑白棋子數相等。

輸出 Output

輸出最少需要移動的次數，如果不能從初始的狀態移動到最終的狀態輸出?1$-1$。

樣例輸入 Sample Input

3 w*b #*w b** b*w #w* **b

樣例輸出 Sample Output

5

限制 Limits

對于20%$20/%$的數據，保證N=2$N=2$ 。 對于50%$50/%$的數據，保證2≤N≤3$2/le N/le 3$。 對于100%$100/%$的數據，保證2≤N≤4$2/le N/le 4$。 Time Limit : 5s$5s$ & Memory Limit : 256MB$256MB$

在做題之前，請注意這句話：

棋子每次移動只有當遇到棋盤邊界，棋盤中的障礙或者其他的棋子時才會停止。

我也不知道為什么要注意這句話 聽說考試的時候有人被坑了？ 5s$5s$不虛，直接BFS，再搞搞狀態描述。棋盤上狀態可以用n2$n^2$位的三進制數描述（分別是w，b，*。#可以忽略并特殊標記），最大的狀態是∑16i=13i+1$/sum_{i=1}^{16}3^{i+1}$，用哈希大法搞定判重即可。 題解中給出了用Tire數完成這種哈希的方法，挺神的。不過我覺得還是直接點好 關于先移動白棋，再移動黑棋，可以發現，奇數步移動白棋，偶數步移動黑棋，這樣就可以根據步數的奇偶性判斷應該移動的棋子。 時間玄學。 Code