迷宫最短路用BFS，为什么不能用DFS

做题时用DFS走迷宫，答案对了但超时；换成BFS立刻过。当时不服气：都是遍历，凭什么差这么多。把两者的搜索过程画在纸上比了一遍，才真正看明白层序展开的意义。

核心差异

BFS按层扩散：先访问距起点0步的，再1步、2步，第一次到达某点时，走过的步数一定是最短的。DFS一条道走到黑，找到的第一条路径可能绕了远路，必须搜完所有路径才能确认最短，指数级开销。

from collections import deque

def shortest_path(grid, start, end):
    """grid中0是通路1是墙，返回起点到终点步数"""
    rows, cols = len(grid), len(grid[0])
    dist = {start: 0}
    q = deque([start])
    while q:
        r, c = q.popleft()
        if (r, c) == end:
            return dist[(r, c)]
        for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and grid[nr][nc] == 0
                    and (nr, nc) not in dist):
                dist[(nr, nc)] = dist[(r, c)] + 1
                q.append((nr, nc))
    return -1   # 不可达

入队时立刻标记距离，而不是出队时——否则同一节点会被重复入队好几次，队列爆炸。

什么时候BFS不灵

边权不全是1时，「先到即最短」失效：一条绕两步的高速路可能比一条一步的土路更近。这时换Dijkstra（非负权，优先队列每次取当前最近点），再进一步有负权用Bellman-Ford/SPFA。BFS是Dijkstra在所有边权为1时的特例，理解这层关系，选型就不会错。

双向BFS

起点和终点同时扩散，两边碰头即停。搜索空间从b^d降到2·b^(d/2)，d为答案深度。无权图上求两点距离，地图一大就值得上这个优化，迷宫游戏里做寻路，双向BFS加边界剪影是常见组合。

DFS的主场

DFS并非不如BFS，是分工不同：要枚举所有路径、回溯找全部解、检测环、拓扑排序、走迷宫「任意一条」路，DFS更顺手且空间只要递归深度。判断标准就一条：要最短且边权相同，选BFS；要遍历所有可能，选DFS加剪枝。当时的超时让我记住了这句话，也顺便记住了队列标记入队时机这个隐蔽的坑。