4072: 骑士问题(knight)

【问题描述】

在一个标准8×8的国际象棋棋盘上，棋盘中有些格子可能是有障碍物的。已知骑士的初始位置和目标位置，你的任务是计算出骑士最少需要多少步可以从初始位置到达目标位置。有障碍物的格子当然不可以到达。
标准的8×8的国际象棋棋盘中每一个格子可以用唯一的编号确定。行用1～8这8个数字依次表示，列用“a”～“h”这8个字母依次表示。例如图8.4-4的骑士所在位置（图中有n的格子）的编号为“d4”（注意“d”和“4”之间没有空格）。

我们知道国际象棋中的骑士可以按“L”路线移动（一个方向走2个格子，接着垂直方向走1个格子）。因此，图8.4-4中的骑士（位于d4），可以到达位置c2、b3、b5、c6、e6、f5、f3和e2（图中有“x”）标记的格子。此外，骑士不能移出棋盘。

骑士可以按照移动规则自由地在棋盘上没有障碍物的格子中移动，图中给出了一个骑士移动的例子。初始格子用“n”标记，目标格子用“N”标记，有障碍物的格子用“b”标记。一个可行的移动序列在图中用数字标记出来。（a1，b3，a5，c6，e5，g4，h2，f1）。总共需要7步才能完成。事实上，这也就是最小的步数了。

【输入格式】

输入文件包括1个或多个测试数据。

每一个测试数据的第一行是一个整数b(-1≤b≤62)，表示棋盘中有障碍物的格子数目，当b=-1时，输入文件结束。

第二行含b个不同的有障碍物的格子编号，用空格隔开。当b=0时，此行为空行。

第三行是骑士的初始格子和目标格子的编号，也是用空格隔开。初始格子和目标格子是不同的，且都没有障碍物。

【输出格式】

对于每个数据，输出一行。格式：Board n: m moves，其中n表示数据的序号（从1开始）m表示骑士所用的最小的步数。如果骑士无法到达目标格子，输出：Board n: not reachable。

【输入样例】

10

c1 d1 d5 c2 c3 c4 d2 d3 d4 c5

a1 f1

0

c1 b3

2

b3 c2

a1 b2

-1

【输出样例】

Board 1: 7 moves

Board 2: 1 moves

Board 3: not reachable