Walls and Gates

Problem: Walls and Gates

The basic idea is to do breath-first search from gates.

Code in Python:

from collections import deque

class Solution(object):
    def wallsAndGates(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: void Do not return anything, modify rooms in-place instead.
        """
        if not rooms: return
        m, n = len(rooms), len(rooms[0])
        for i in xrange(m):
            for j in xrange(n):
                if rooms[i][j] != 0:
                    continue

                queue = deque([(i, j, 0)])
                while queue:
                    x, y, level = queue.popleft()
                    rooms[x][y] = level
                    if x > 0 and rooms[x-1][y] != -1 and rooms[x-1][y] > level+1: queue.append((x-1, y, level+1))
                    if y > 0 and rooms[x][y-1] != -1 and rooms[x][y-1] > level+1: queue.append((x, y-1, level+1))
                    if x < m-1 and rooms[x+1][y] != -1 and rooms[x+1][y] > level+1: queue.append((x+1, y, level+1))
                    if y < n-1 and rooms[x][y+1] != -1 and rooms[x][y+1] > level+1: queue.append((x, y+1, level+1))