BFS求解路径与怪物最小距离最大化问题的代码修复

玩家在n*m的2D网格上，起点为S，终点为E，网格中存在多个怪物X。目标是找到一条从起点到终点的路径，使得路径上任意点与最近怪物的最小距离尽可能大。现有BFS代码仅能通过部分测试用例，例如测试用例findBestPath(5, 5, 0, 0, 4, 3, {0,0,3}, {3,4,4})返回错误结果2，需排查并修复代码问题。

示例：起点S=(0,0)，终点E=(3,3)，怪物X=((0,3),(1,2))，正确答案为2。

原代码 #

def findBestPath(n, m, startRow, startColumn, endRow, endColumn, monsterRow, monsterColumn):
    # n是行数，m是列数
    # 从怪物位置开始逐层扩展计算距离
    d = [[None]*m for i in range(n)]
    curr = set(zip(monsterRow, monsterColumn))
    deck = set()
    dist = 0
    while curr:
        for r, c in curr:
            d[r][c] = dist
        for r, c in curr:
            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < m:
                    if d[nr][nc] is None:
                        deck.add((nr, nc))
        curr = deck
        deck = set()
        dist += 1
    # 从起点开始的改进型 floodfill
    visited = [[False]*m for i in range(n)]
    target = (endRow, endColumn)
    curr = {(startRow, startColumn)}
    mindist = d[startRow][startColumn]
    deck = set()
    succ = set()
    while mindist >= 0:
        while curr:
            for r, c in curr:
                if (r, c) == target:
                    return mindist
                visited[r][c] = 1
            for r, c in curr:
                for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < m:
                        if not visited[nr][nc]:
                            np = (nr, nc)
                            dist = d[nr][nc]
                            if dist >= mindist:
                                deck.add(np)
                            elif dist == mindist - 1:
                                succ.add(np)
            curr = deck
            deck = set()
        mindist -= 1
        curr = succ
        deck = set()
        succ = set()

print(findBestPath(5, 5, 0, 0, 4, 3, {0,0,3},{3,4,4})) # 怪物的行坐标列表、列坐标列表

原代码问题分析 #

1. 访问标记过早设置：在处理当前层节点时直接标记为已访问，导致后续无法通过更优（离怪物更远）的路径到达该节点，丢失最优解可能。
2. 路径搜索逻辑缺陷：按mindist从高到低逐层处理，但未考虑同一层节点的扩展方向差异，且收集下一层节点的方式会遗漏可行路径，无法保证找到最大的最小距离。

修复后的代码 #

import heapq
from collections import deque

def findBestPath(n, m, startRow, startColumn, endRow, endColumn, monsterRow, monsterColumn):
    # 第一步：多源BFS计算每个点到最近怪物的距离
    dist_to_monster = [[-1]*m for _ in range(n)]
    q = deque()
    # 初始化怪物位置，距离为0
    for r, c in zip(monsterRow, monsterColumn):
        if dist_to_monster[r][c] == -1:  # 避免重复添加同一怪物位置
            dist_to_monster[r][c] = 0
            q.append((r, c))
    
    dirs = [(0,1), (0,-1), (1,0), (-1,0)]
    while q:
        r, c = q.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < m and dist_to_monster[nr][nc] == -1:
                dist_to_monster[nr][nc] = dist_to_monster[r][c] + 1
                q.append((nr, nc))
    
    # 第二步：最大堆优先搜索，每次选当前路径最小距离最大的节点扩展
    max_min_dist = [[-1]*m for _ in range(n)]
    heap = []
    start_min_dist = dist_to_monster[startRow][startColumn]
    heapq.heappush(heap, (-start_min_dist, startRow, startColumn))
    max_min_dist[startRow][startColumn] = start_min_dist
    
    while heap:
        neg_dist, r, c = heapq.heappop(heap)
        current_min = -neg_dist
        # 到达终点，直接返回（最大堆保证首次到达时的距离就是最优解）
        if r == endRow and c == endColumn:
            return current_min
        # 已有更优路径，跳过当前节点
        if max_min_dist[r][c] > current_min:
            continue
        # 扩展四个方向
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < m:
                # 新路径的最小距离是当前节点与下一个节点距离的最小值
                new_min = min(current_min, dist_to_monster[nr][nc])
                # 如果新路径更优，更新并加入堆
                if new_min > max_min_dist[nr][nc]:
                    max_min_dist[nr][nc] = new_min
                    heapq.heappush(heap, (-new_min, nr, nc))
    
    # 无法到达终点时返回-1（题目默认存在路径可忽略此情况）
    return -1

# 测试用例
print(findBestPath(5, 5, 0, 0, 4, 3, {0,0,3}, {3,4,4}))
# 示例测试
print(findBestPath(4,4,0,0,3,3, {0,1}, {3,2})) # 应返回2

修复说明 #

1. 多源BFS优化：改用deque实现高效BFS，避免重复处理同一怪物位置，确保距离计算准确。
2. 最大堆路径搜索：通过优先队列每次选择当前最优（路径最小距离最大）的节点扩展，保证首次到达终点时的距离即为所求最大值。
3. 路径记录优化：每个节点记录能到达的最大最小距离，避免重复处理更差的路径，提升效率与正确性。

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