当棋盘上有棋子时计算骑士最短路径的 Pythonic 方法

Question

在学习面试的过程中，遇到了这个问题，我看懂了，但是不知道怎么解决。

假设你有这个板（在这种情况下是 4 行 3 列的矩阵，但它可以是 N 行和 M 列长）

A[0][0] = 0    A[0][1] = 0    A[0][2] = 0
A[1][0] = 0    A[1][1] = 0    A[1][2] = 1
A[2][0] = 1    A[2][1] = 0    A[2][2] = 0
A[3][0] = 0    A[3][1] = 0    A[3][2] = 0

你如何计算马从左上角的方格走到右下角的最少转数？

0 表示该方格上没有棋子，1 表示该方格上有棋子。

在这种情况下，骑士需要7轮才能移动到右下角：

in the first turn the knight moves from square (0, 0) to square (2, 1); 
in the second turn the knight moves from square (2, 1) to square (0, 2); 
in the third turn the knight moves from square (0, 2) to square (1, 0); 
in the fourth turn the knight moves from square (1, 0) to square (2, 2);  
in the fifth turn the knight moves from square (2, 2) to square (3, 0);  
in the sixth turn the knight moves from square (3, 0) to square (1, 1);  
in the seventh turn the knight moves from square (1, 1) to square (3,4).

最好的情况显然是 3，但那些方块（A[1][2] 和 A[2][0]）被挡住了。

实现它的最佳方法是什么？我在网上看到 BFS 可以做到这一点，但我什至不知道从哪里开始编码 Python。提前致谢。

函数应该如下所示：

 def shortest_path(matrix):
     #passing in [[0, 0, 0], [0, 0, 1], [1, 0, 0], [0, 0, 0]]

Answer 1

将棋盘上每个未被占用的方格想象成图中的一个节点，边连接方格，骑士可以在一个回合内在这些方格之间移动。然后你可以使用你选择的搜索算法来找到这个图中的最短路径。

当棋盘上有棋子时计算骑士最短路径的 Pythonic 方法

Pythonic way to calculate the shortest path for a knight when board has pieces on it

python

algorithm

graph

minimization

shortest-path