网格最优避障路径最小距离求解及DP+BFS超时优化

给定网格（.表示可移动位置，*表示障碍物，S和E分别表示起点和终点），需找到从起点到终点的最优路径（最大化与所有障碍物的距离）中，路径上任意点到障碍物的最小曼哈顿距离。若起点到终点无路径则返回0；若存在路径，例如路径上到障碍物的最近距离为2，则返回2。

我尝试先通过DP计算网格中每个点到最近障碍物的距离，再使用优先队列执行BFS，但仍遇到超时问题，请问还有哪些优化方法？

示例输入 #

5
..*
.S.
..*
...
..E

答案：2
最优路径为(1,1) -> (1,0) -> (2,0) -> (3,0) -> (4,0) -> (4,1) -> (4,2)，路径上到障碍物的最近距离为2。

我的实现代码 #

from collections import deque
from queue import PriorityQueue
import math  # 补充原代码遗漏的导入
  
def findMaximumDistance(grid):
    matrix = []
    new_matrix = []
    for row in grid: 
        matrix.append(list(row))
        row = [1 if ele != '*' else 0 for ele in row]
        new_matrix.append(list(row))

    # 标记起点和终点
    m, n = len(matrix), len(matrix[0])
    start = None
    end = None
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 'S':
                start = (i,j)
            elif matrix[i][j]== 'E':
                end = (i,j)

    def updateMatrix(mat):
        m, n = len(mat), len(mat[0])

        for r in range(m):
            for c in range(n):
                if mat[r][c] > 0:
                    top = mat[r - 1][c] if r > 0 else math.inf
                    left = mat[r][c - 1] if c > 0 else math.inf
                    mat[r][c] = min(top, left) + 1

        for r in range(m - 1, -1, -1):
            for c in range(n - 1, -1, -1):
                if mat[r][c] > 0:
                    bottom = mat[r + 1][c] if r < m - 1 else math.inf
                    right = mat[r][c + 1] if c < n - 1 else math.inf
                    mat[r][c] = min(mat[r][c], bottom + 1, right + 1)

        return mat

    new_matrix = updateMatrix(new_matrix)

    def best_first_search():
        nonlocal min_dist
        visited = []
        DIR = [0, 1, 0, -1, 0]
        pq = PriorityQueue()
        pq.put((-new_matrix[start[0]][start[1]], start))
        
        while pq:
            dist, pos = pq.get()
            dist = -dist
            r, c = pos
            min_dist = min(min_dist, dist)
            visited.append((r,c))
            if pos == end:
                break
            for i in range(4):
                nr, nc = r + DIR[i], c + DIR[i + 1]
                if nr < 0 or nr == m or nc < 0 or nc == n or (nr,nc) in visited: continue
                pq.put((-new_matrix[nr][nc],(nr, nc)))
    
    min_dist = float('inf')    
    best_first_search()
    return min_dist if min_dist != float('inf') else 0

1. 替换DP为多源BFS计算距离 #

你当前用DP计算的是网格最短路径步数（切比雪夫距离），如果题目要求曼哈顿距离，需要调整计算逻辑；如果是网格最短路径距离，多源BFS更高效且准确，时间复杂度同为O(mn)，但避免DP的两次遍历误差：

def updateMatrix(mat):
    m, n = len(mat), len(mat[0])
    q = deque()
    dist = [[-1]*n for _ in range(m)]
    # 初始化所有障碍物的距离为0并加入队列
    for i in range(m):
        for j in range(n):
            if mat[i][j] == 0:
                dist[i][j] = 0
                q.append((i,j))
    # 多源BFS扩散计算最短距离
    dirs = [(-1,0),(1,0),(0,-1),(0,1)]
    while q:
        x, y = q.popleft()
        for dx, dy in dirs:
            nx, ny = x+dx, y+dy
            if 0<=nx<m and 0<=ny<n and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
    return dist

2. 替换PriorityQueue为heapq #

queue.PriorityQueue是线程安全实现，自带锁机制导致速度较慢，换成heapq模块实现优先队列，能显著提升执行效率：

import heapq

# 在BFS中替换队列实现
pq = []
heapq.heappush(pq, (-new_matrix[start[0]][start[1]], start[0], start[1]))

3. 优化visited结构 #

原代码用列表存储已访问节点，(nr,nc) in visited是O(k)时间复杂度，换成二维布尔数组后判断时间降为O(1)，这是核心性能优化点：

# 初始化二维visited数组
visited = [[False]*n for _ in range(m)]
visited[start[0]][start[1]] = True

# 遍历邻接节点时的判断
if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
    visited[nr][nc] = True
    heapq.heappush(pq, (-new_matrix[nr][nc], nr, nc))

4. 记录节点最优状态，避免重复处理 #

当前代码的全局min_dist更新逻辑存在缺陷，需为每个节点记录能达到的最大路径最小距离，如果新路径的该值不大于已记录值，直接跳过该节点，减少无效队列操作：

def best_first_search():
    dirs = [(-1,0),(1,0),(0,-1),(0,1)]
    # 记录每个节点的最优路径最小距离
    max_min_dist = [[-1]*n for _ in range(m)]
    max_min_dist[start[0]][start[1]] = new_matrix[start[0]][start[1]]
    pq = []
    heapq.heappush(pq, (-max_min_dist[start[0]][start[1]], start[0], start[1]))

    while pq:
        neg_dist, r, c = heapq.heappop(pq)
        current_min = -neg_dist
        # 若当前路径不是最优，直接跳过
        if current_min < max_min_dist[r][c]:
            continue
        # 到达终点直接返回结果
        if (r,c) == end:
            return current_min
        for dx, dy in dirs:
            nr, nc = r+dx, c+dy
            if 0<=nr<m and 0<=nc<n:
                new_min = min(current_min, new_matrix[nr][nc])
                # 仅当新路径更优时才更新并加入队列
                if new_min > max_min_dist[nr][nc]:
                    max_min_dist[nr][nc] = new_min
                    heapq.heappush(pq, (-new_min, nr, nc))
    return 0

5. 提前终止与边界处理 #

• 若起点或终点被障碍物包围（无法抵达），直接返回0；
• BFS过程中一旦弹出终点节点，立即返回当前结果，无需处理队列剩余元素。

内容的提问来源于stack exchange，提问作者ViridTomb