题目描述：
下过象棋的人都知道，马只能走’日’字形（包括旋转90°的日），现在想象一下，给你一个n行m列网格棋盘， 棋盘的左下角有一匹马，请你计算至少需要几步可以将它移动到棋盘的右上角，若无法走到，则输出-1. 如n=1，m=2,则至少需要1步；若n=1，m=3,则输出-1。
分析
图形的搜索算法常见的有两种：深度优先（DFS）和 广度优先（BFS）
以下图为例说明两种算法的不同之处：
深度优先 不断沿着顶点的深度方向遍历，直到没有邻接点时再返回。
访问顺序： A-B-D-E-C-F-H-G
例如这里： 第一次从A到达B点时，还可以向 D 点访问，所以先访问点D。
访问完点D后，发现没有邻接点了，就返回到点B，然后再访问点E。
访问点E后，没有邻接点，就返回到点B，返回到点B的时候，发现下面的两个点都已经访问，就返回到点A。
然后从点A遍历到点C，再从C到F，再从F到H。最后访问点G。
广度优先
先访问与一个节点相邻的所有结点并且加入队列，然后再访问下一个节点。
访问顺序： A-B-C-D-E-F-G-H
解释：先访问和点A相邻的就是点 B 和 点 C。 队列： BC
然后从点B开始，访问到点DE, 队列 CDE
再从点C开始，访问到点 DEFG
然后…….
这就是我们深度优先和广度优先的两种遍历的结果。如果有兴趣，或者还不够明白，可以看看这个 https://www.jianshu.com/p/bff70b786bb6。
对于此题我们选用其中任何一种算法都是可以实现的。但是由于深度优先的遍历方式，我们需要遍历所有的节点才直到最少的步数是多少步。
如果是广度优先我们只需要遍历到 终点就可以返回了。因为我们是一层一层的去访问的，每一层就相当于一步，先找到一步能到的所有位置。
再找到两步可以到的所有位置。这样的话，我们就有可能少遍历一些点。这样就可以节约一点遍历的时间。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 当前的 马 可以去的8个位置， 相当于8 个方向
direction = [(-2, 1), (-2, -1), (2, 1), (2, -1), (-1, 2), (1, 2), (-1, -2), (1, -2)]
from queue import Queue
que = Queue()
# 开始位置 和 结束位置
now_x, now_y = n, 0
end_x, end_y = 0, m
# 我有这个，就可以同时记录 是否已经走过，还有 当前步数了
steps = {}
# 还要一个记录 当前是 第几步的操作。 想一想，，，
# 初始化， 将第一个位置加入队列
que.put((now_x, now_y))
steps[(now_x, now_y)] = 0
min_step = -1
while not que.empty():
now_x, now_y = que.get()
for dx, dy in direction:
tx = now_x + dx
ty = now_y + dy
if tx > n or tx < 0 or ty > m or ty < 0:
continue
if tx == end_x and ty == end_y:
min_step = steps[(now_x, now_y)] + 1
break
if (tx, ty) in steps.keys():
continue
steps[(tx, ty)] = steps[(now_x, now_y)] + 1
que.put((tx, ty))
if min_step > 0:
break
print(min_step)