「HLOI2016」黑白棋

Posted on In
HLOI2016 Day1 T3

题目描述

有这样一种有趣的棋类游戏，假设有一个 N × N 方格的棋盘，棋盘中存在障碍格，即该格子不能放置棋子。棋盘上有若干个白色棋子和黑色棋子随机摆放，每个格子只能放一个棋子。现在你知道棋盘的初始状态和最终状态，请问最少需要移动几次棋子才能从初始状态达到最终状态。棋子的移动规则如下:

  1. 每次选择一枚棋子进行移动；
  2. 必须先移动白棋，按照先白棋后黑棋的顺序交替进行；
  3. 每次选择的棋子可以在水平、垂直以及对角线共计八个方向中的任意方向上移动，棋子每次移动只有当遇到棋盘边界，棋盘中的障碍或者其他的棋子时才会停止；
  4. 棋盘中的障碍格不能移动。

输入

第一行给出 N。

接下来输入包括 2 × N 行，每行 N个字符。前 N 行表示棋盘的初始状态，后 N 行表示棋盘的最终状态。

字符 w 表示白色棋子，字符 b 表示黑色棋子，字符 # 表示棋盘中的障碍，字符 * 表示棋盘中的空格。保证黑白棋子数相等。

输出

输出最少需要移动的次数，如果不能从初始的状态移动到最终的状态输出  − 1。

样例输入

1
2
3
4
5
6
7
3
w*b
#*w
b**
b*w
#w*
**b

样例输出

1
5

数据范围及约定

对于 20% 的数据，保证 N = 2。

对于 50% 的数据，保证 2 ≤ N ≤ 3。

对于 100% 的数据，保证 2 ≤ N ≤ 4。

时间与空间限制

时间限制：5000ms，空间限制：256MB。

题解

在做题之前，请注意这句话：

棋子每次移动只有当遇到棋盘边界，棋盘中的障碍或者其他的棋子时才会停止。

我也不知道为什么要注意这句话，听说考试的时候有人被坑了？

五秒不虚，直接 BFS，再搞搞状态描述。棋盘上状态可以用 n2 位的三进制数描述（分别是 w，b，*。# 可以忽略并特殊标记），最大的状态是 ，用哈希大法搞定判重即可。

题解中给出了用 Tire 树完成这种哈希的方法，挺神的。不过我觉得还是直接点好

关于先移动白棋，再移动黑棋，可以发现，奇数步移动白棋，偶数步移动黑棋，这样就可以根据步数的奇偶性判断应该移动的棋子。

时间空间玄学。

代码见这里。