Problem:

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 value2^31 - 1 = 2147483647to represent INF as you may assume that the distance to a gate is less than2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled withINF.

Solution:

Use bfs, breadth first search, to iterate thru all the rooms on the grid. For each room distance examination, go through all its different levels of neighbors to find the exit. Remember to create a "visited" set so that we don't revisit old rooms.

Python Code:

# @param {int[][]} rooms m x n 2D grid
    # @return {void} nothing, modify in-place
    def wallsAndGates(self, rooms):
        # Write your code here
        if rooms == []:
            return 
        numRows = len(rooms)
        numCols = len(rooms[0])

        for row in range(numRows):
            for col in range(numCols):
                self.bfs(rooms, row, col)




    def bfs(self, rooms, row, col):
        if rooms[row][col] <= 0 :
            return
        visited = set()
        q = [(row, col)]
        steps = 0
        while q:
            new_q = []
            while q:

                r,c = q.pop(0)
                visited.add( (r,c))
                if rooms[r][c] == 0:
                    rooms[row][col] = steps
                    return
                elif rooms[r][c] == -1:
                    continue
                else:
                    new_q.extend(self.getValidNeighbors(rooms, r, c, visited))
            q = new_q
            steps += 1

    def getValidNeighbors(self, rooms, row, col, visited):
        numRows = len(rooms)
        numCols = len(rooms[0])
        res = []
        if row - 1 >= 0 and (row-1, col) not in visited:
            res.append( (row-1, col))
        if row + 1 < numRows and (row+1, col) not in visited:
            res.append( (row+1, col))
        if col - 1 >= 0 and (row, col-1) not in visited:
            res.append( (row, col-1))
        if col + 1 < numCols and (row, col+1) not in visited:
            res.append( (row, col+1))
        return res

Complexity:

m is width of grid, n is height of grid

time: O(m*n) on average, O((m*n)^2) for worst case

Space: two queues to be maintained during BFS. thus O(4) on average