python - 如何在 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 的空间中，您无法进入该空间。那么上图中，一条可能的路线可能是这样的:(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) 处，则应返回 -1 或以其他方式指示不路径是可能的。)

Answer 1

正如对您问题的评论所暗示的那样(建议 A* search algorithm )，您希望将其构建为图论/网络问题:

• 网格上的每个位置都是一个节点
• 如果正好有一个坐标相差 1，则节点共享一条边
• X 个节点(及其关联的边)被删除

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