n行m列网络棋盘，棋子只能走日字形，从左下角至少需要几步可以移动到棋盘的右上角？

Question

题目来源：http://www.pythontip.com/codi...

问题描述：

下过象棋的人都知道，马只能走'日'字形（包括旋转90°的日），现在想象一下，给你一个n行m列网格棋盘，棋盘的左下角有一匹马，请你计算至少需要几步可以将它移动到棋盘的右上角，若无法走到，则输出-1.如n=1，m=2,则至少需要1步；若n=1，m=3,则输出-1。

思路：

马走日，从某一点开始走，一共有8种走法：

题目要求从左下走到右上，那么能用上的就是坐标轴第一和第四象限的4种走法，需要根据实际位置判断马下一步怎么走，而且走的总步数最少，需要使用广度优先遍历从某一步到下一步的所有走的路径，还需要记录步长，考虑最短路径。 算法能力比较差，代码的具体编写没写出来。

这是关于这道题的解题报告：http://www.pythontip.com/codi...

里面的思路有给广度优先加剪枝的，还有用向量的，但是有4层for循环复杂度太高。

希望可以帮忙分析下这道题，谢谢大家。

Answer 1

既然是计算最小步数，确实是可以使用广度优先的算法来计算。如果你不太了解广度优先算法具体是什么，建议先google了解算法。

1. 首先我们需要一个队列Q存储待访问的点，一个map记录访问过的点visited[maxL][maxH]，起始点为vs=[0,0,0]0,1两点记录坐标，2点记录index步长, 结束点为vd=[n,m], Q.append(vs), 把起始点丢进队列里。
2. 马走日，创建两个list列出x和y可走的方向dx=[1,1,2,2,-1,-1,-2,-2], dy=[2,-2,1,-1,2,-2,1,-1]
3. while Q: 只要有未访问的点，就执行循环。
4. vn=Q.pop(0), 取出队列第一个点并抛掉, if [vn[0],vn[1]] == vd: return vn[2] 如果发现此点就是想要的点，直接返回index步长，得到结果。
5. 如果不是结果，就寻找与此节点相邻的未访问的点：

    for (x,y) in zip(dx,dy): #我这边用了zip打包dx，dy。也可以直接就写成二维
      vnx=vn[0]+x  # for循环出所有可能的下一个节点
      vny=vn[1]+y
      index=vn[2]+1 # 步长为vn的步长+1，就是上一个节点的index+1
      if 0<=vnx<=n and 0<=vny<=m and visited[vnx][vny] != 1: # 判断是否超出边界，是否已经访问过
        visited[vnx][vny] = 1  # 标记节点已访问，并插入队列Q
        Q.append([vnx, vny, index])

• 最后检索完毕没有找到结果，return -1

方法仅供参考，虽然过了你那个题目的测试。