2258.md

2258. Escape the Spreading Fire

Solution 1 (time O(mn), space O(mn))

# BFS
class Solution(object):
    def maximumMinutes(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])

        def bfs(q):
            time = [[-1] * n for _ in range(m)]
            for i, j in q:
                time[i][j] = 0
            t = 1
            while q:
                new_q = []
                for i, j in q:
                    for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                        if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and time[x][y] < 0:
                            time[x][y] = t
                            new_q.append((x, y))
                q = new_q
                t += 1
            return time[-1][-1], time[-1][-2], time[-2][-1]
        
        people_time1, people_time2, people_time3 = bfs([(0, 0)])
        if people_time1 < 0:
            return -1
        fire_pos = [(i, j) for i, row in enumerate(grid) for j, x in enumerate(row) if x == 1]
        fire_time1, fire_time2, fire_time3 = bfs(fire_pos)
        if fire_time1 < 0:
            return 10 ** 9
        d = fire_time1 - people_time1
        if d < 0:
            return -1
        if (people_time2 != -1 and people_time2 + d < fire_time2) or (people_time3 != -1 and people_time3 + d < fire_time3):
            return d
        return d - 1