Walls and Gates

Question Description

You are given a m x n 2D grid 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 $$2^{31} - 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.

Solution

Because we need to find the shortest distance, and we have a matrix, the first thing we should think about is Breath First Search.

Then we need to check every position whose value is 0 to update its reachable rooms. But we also need to do pruning to avoid TLE.

*Here we found a very smart pruning from Googling in which it only update the room whose value is bigger than the current position value plus one.

class Solution(object):
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: void Do not return anything, modify rooms in-place instead.
        """
        m = len(rooms)
        if m == 0: return
        n = len(rooms[0])
        if n == 0: return
        q, dirs = [], [(-1,0), (1,0), (0,-1),(0,1)]
        for i in range(m):
            for j in range(n):
                if rooms[i][j] == 0:
                    q.append((i,j))
        while len(q) > 0:
            coordx, coordy = q.pop(0)
            for dire in dirs:
                dx, dy = dire
                x, y = coordx + dx, coordy + dy
                if self.valid(x, y, rooms) and rooms[x][y] > rooms[coordx][coordy] + 1:
                    rooms[x][y] = rooms[coordx][coordy] + 1
                    q.append((x, y))

    def valid(self, i, j, rooms):
        return i >= 0 and i < len(rooms) and j >= 0 and j < len(rooms[0])