leetcode - 286. Walls and Gates

Description

You are given an m x n grid rooms initialized with these three possible values.

• -1 A wall or an obstacle.
• 0 A gate.
• INF Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Example 1:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Example 2:

Input: rooms = [[-1]]
Output: [[-1]]

Constraints:

m == rooms.length
n == rooms[i].length
1 <= m, n <= 250
rooms[i][j] is -1, 0, or 2^31 - 1.

Solution

Bellman-ford algorithm, update until there is no update.

Time complexity: $o(n^2)$?
Space complexity: $o(n^2)$

Code

class Solution:
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        """
        Do not return anything, modify rooms in-place instead.
        """
        queue = collections.deque([])
        room_cnt, room_distance = 0, {}
        m, n = len(rooms), len(rooms[0])
        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    queue.append((i, j, 0))
                elif rooms[i][j] == 2147483647:
                    room_cnt += 1
                    room_distance[(i, j)] = 2147483647
        while queue:
            x, y, dis = queue.popleft()
            if rooms[x][y] == 0 and dis > 0:
                continue
            if (x, y) in room_distance:
                if room_distance[(x, y)] > dis:
                    room_distance[(x, y)] = dis
                else:
                    continue
            for dz in (-1, 1):
                if 0 <= x + dz < m and rooms[x + dz][y] != -1:
                    queue.append((x + dz, y, dis + 1))
                if 0 <= y + dz < n and rooms[x][y + dz] != -1:
                    queue.append((x, y + dz, dis + 1))
        for (x, y), dis in room_distance.items():
            if dis != 2147483647:
                rooms[x][y] = dis