【算法】【Pyhton】走迷宫-广度优先搜索BFS求解最短路径 - AI科研编程读书笔记

本文介绍利用广度优先搜索（BFS）算法求解迷宫最短路径的Python实现。通过读取用户输入的迷宫矩阵和起止坐标，程序使用队列结构逐层扩展探索路径。每次从队列取出当前坐标后，会向上下左右四个方向进行合法边界检测（不越界且为可行走区域），将符合条件的新坐标标记为已访问并加入队列。由于BFS具有逐层扩散的特性，首个到达终点的路径即为最短路径。当队列耗尽仍未找到终点时返回-1。该实现通过动态修改迷宫矩阵值的方式避免重复访问，时间复杂度为O(nm)，能有效处理常规规模的迷宫问题。

n, m = map(int, input().split())
gra = [list(map(int, input().split())) for i in range(n)]
dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
x1, y1, x2, y2 = map(int, input().split())
q = [[x1 - 1, y1 - 1, 0]]
f = True
while q:
    x, y, dis = q.pop(0)
    if x == x2 - 1 and y == y2 - 1:
        f = False
        print(dis)
        break
    for xx, yy in dirs:
        tx, ty = xx + x, yy + y
        if tx >= 0 and tx < n and ty >= 0 and ty < m and gra[tx][ty] == 1:
            gra[tx][ty] = 0
            q.append([tx, ty, dis+1])
if f: print(-1)

BFS算法是一种用于遍历或搜索树或图的算法。它从根节点（或起始节点）开始，逐层地对节点进行访问，先访问距离起始节点最近的所有节点，然后再访问距离稍远的节点，以此类推。

代码中先获取输入信息，构建四个方向的dirs列表，模拟队列的q列表和判断是否到达的f变量。只要队列中有元素，就循环。

进入循环后出队，获取元素的位置和步数信息。接下来判断这个元素的位置是否到达了终点，如果到达直接设置f为Fasle并打印出距离，跳出循环。若没有到达，接下来遍历四个方向的dirs列表，对当前位置向四个方向拓展，如果拓展后的位置合法（在迷宫内且为道路），那么就把它加入队列中，且设置之前的位置为障碍（防止返回）。

之后就一直从队列中寻找解，一层一层逐层往外扩展，最终找到解。

若无特殊说明，文章版权归作者所有，请勿转载至任何平台。

THE END