如何在 5x5 矩阵中找到 (0,0) 和 (4,4) 之间的最短路线，每步给定一个水平或垂直平移

Question

我编写了以下代码来描述我心中的问题：

row = int(input("How many rows? "))
column = int(input("How many columns? "))
sample_map = []
to_append =[]
for i in range(row):
    for j in range(column):
        to_append.append("_")
    sample_map.append(to_append)
    to_append=[]

def add_to_map(indicator=input("What symbol do you want to use? ")):
    x_coordinate = int(input("Input x coordinate. Note: (0,0) starts at top left. "))-1
    y_coordinate = int(input("Input y coordinate. "))-1

    sample_map[x_coordinate][y_coordinate] = indicator

continue_to_add =input("Do you want to add something to the map? Answer yes or no. ")
while(continue_to_add=="yes"):
    add_to_map()
    continue_to_add =input("Do you want to add something else to the map? Answer yes or no. ")

sample_map[0][0] = "S"
sample_map[row-1][column-1] = "E"

for element in sample_map:
    print(element)

考虑以下输出：

在有 X 的 space 中，您不能进入那个 space。所以在上图中，一条可能的路线可能是这样的： (0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(2,3)->(3,3)->( 4,3)->(4,4)

一共八个步骤。理想情况下，代码应该能够适应给定图表上 X 位置变化的路径。

如果 X 以阻止任何移动的方式出现（即 X 位于 (0,1)、(1,1) 和 (1,0)，则它应该 return -1 或以其他方式表明没有路径是可能的。）

Answer 1

正如对您问题的评论所暗示的（建议 A* search algorithm），您希望将其构建为 图 theory/network 问题：

网格上的每个位置都是一个节点
如果恰好一个坐标恰好相差 1，则节点共享一条边
X 个节点（及其关联的边）已删除

那么问题就变成了，求图中两个节点之间的最短路径。如果节点不在同一个连通分量中，则没有这样的路径。

如何在 5x5 矩阵中找到 (0,0) 和 (4,4) 之间的最短路线，每步给定一个水平或垂直平移

How to find the shortest route between (0,0) and (4,4) in a 5x5 matrix, given one horizontal or vertical translation per step

python

shortest-path