Problem statement

https://binarysearch.com/problems/Wildfire-Sequel/

Solution

The idea is to:

  1. First run multi-source bfs from all fires and for each cell save the time when fire will reach this place.
  2. Run bfs from person and allow him to only go to the cells where we do not have fire yet.

In fact we can make code compact if we use bfs function with queue: starting queue, check is used for the second pass.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, G):
        m, n, queue = len(G), len(G[0]), deque()
        for i,j in product(range(m), range(n)):
            if G[i][j] == 2: queue.append((0, i, j))
            if G[i][j] == 1: person = (i, j)
            
        times = defaultdict(lambda: float("inf"))

        def bfs(queue, check):
            V = set([(x, y) for _, x, y in queue])
            while queue:
                dist, x, y = queue.popleft()
                if check and x + y in [0, m + n - 2]: return True
                if not check: times[x, y] = dist
                for dx, dy in [[1,0],[-1,0],[0,1],[0,-1]]:
                    if 0<=x+dx<m and 0<=y+dy<n and G[x+dx][y+dy] in [0, 1] and (x+dx, y+dy) not in V:
                        if check and dist >= times[x+dx, y+dy]: continue
                        V.add((x + dx, y + dy))
                        queue.append((dist + 1, x+dx, y+dy))
            return False

        bfs(queue, False)
        return bfs(deque([(0,) + person]), True)