[省选] [BFS] HLOI2016Day1 黑白棋

问题描述 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