骑士问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在一个标准8*8的国际象棋棋盘上,棋盘中有些格子可能是有障碍物的。已知骑士的初始位置和目标位置,你的任务是计算出骑士最少需要多少步可以从初始位置到达目标位置。有障碍物的格子当然不可以到达。

标准的8*8的国际象棋棋盘中每一个格子可以用惟一的编号确定。行用1~8这8个数字依次表示,列用“a”~“h”这8个字母依次表示。例如图1(a)的骑士所在的位置(图中有n个格子)的编号为“d4”(注意“d”和“4”之间没有空格)。 



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

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

Input

输入包括一个或多个测试数据。

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

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

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

Output

对于每个数据,输出一行。格式
 
Board n: m moves

其中n表示数据的序号(从1开始),m表示骑士所用的最小步数。

如果骑士无法到达目标格子,输出
 
Board n: not reachable

Sample Input

10
c1 d1 d5 c2 c3 c4 d2 d3 d4 c5
a1 f1
0

c1 b3
2
b3 c2
a1 b2
-1

Sample Output

Board 1: 7 moves
Board 2: 1 moves
Board 3: not reachable

Hint

Source