骑士遍历问题。原创代码。通过测试的。

--

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

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

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

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