BFS 最大化沿路径与怪物的最小距离

Question

玩家从大小为 n*m 的二维网格开始。 “E”代表玩家试图到达的结束位置，“S”代表开始位置，“X”代表怪物。网格中可以有多个怪物。目标是使用一条路径到达终点单元，该路径最大化与沿该路径的任何怪物的最小距离。

下面的代码适用于某些测试用例，但对于其他许多测试用例没有给出正确的答案。

def findBestPath(n, m, startRow, startColumn, endRow, endColumn, monsterRow, monsterColumn):
    # n is the number of rows, m is the number of columns
    # expand in shells starting from the monster locations
    d = [[None]*m for i in range(n)]
    # set of current location and set of next locations
    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
    # Now do a kind of modified floodfill from the start point.
    # It could be bidirectional but we are lazy.
    # Track three shells: current high-d, on-deck high-d, successor lower-d.
    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})) // list of row positions, list of column positions for monsters

例如：S = (0,0), e = (3,3), X = ((0,3), (1,2)), ans = 2

对于代码中的测试用例，对于findBestPath(5, 5, 0, 0, 4, 3, {0,0,3},{3,4,4})返回2，并且对于这个findBestPath也返回2 (5, 5, 0, 0, 4, 3, {0,0,3},{3,4,3}) 这是错误的

Answer 1

主要问题是您将怪物的坐标作为一组 x 坐标和一组 y 坐标传递。通过将它们定义为集合，您：

• 同一列或同一行不能有两个怪物。意识到

  {3,4,3}

  与

  {3,4}

是同一组
• 不能依赖这些坐标的顺序，这样就有可能将不相关的坐标配对。

解决方法是将这些坐标作为列表传递（附带说明：传递

(x, y)

元组列表更有意义）。

因此，如果您将调用更改为：

print(findBestPath(5, 5, 0, 0, 4, 3, [0,0,3],[3,4,3])) 

...输出将为 1，正如预期的那样（因为目标细胞是怪物细胞的直接邻居）。