BFS Maximize Minimum Distance from a Monster along a path

Question

A player begins on a 2d grid of size n*m. 'E' refers to the end position the the player is trying to get to, 'S' represents the start position and 'X' refers to a monster. There can be multiple monsters in the grid. The goal is to reach the end cell using a path that maximizes the minimum distance from any monster along that path.

The code below works for some test cases but doesnt give the correct answer for many others.

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

Ex: S = (0,0), e = (3,3), X = ((0,3), (1,2)), ans = 2

For the test case in the code, it returns 2 for findBestPath(5, 5, 0, 0, 4, 3, {0,0,3},{3,4,4}) and also returns 2 for this findBestPath(5, 5, 0, 0, 4, 3, {0,0,3},{3,4,3}) which is wrong

Answer 1

The main problem is that you pass the coordinates of the monsters as a set of x-coordinates and a set of y-coordinates. By defining them as sets, you:

• Cannot have two monsters in the same column, nor in the same row. Realise that {3,4,3} is the same set as {3,4}
• Cannot rely on the order of these coordinates, so that you risk to pair up unrelated coordinates.

The fix is to pass these coordinates as lists (as a side note: it would make more sense to pass a list of (x, y) tuples).

So if you alter your call to this:

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

...the output will be 1, as would be the expected (since the target cell is a direct neighbor of a monster cell).