from collections import deque


def walls_and_gates(rooms):
    for i in xrange(len(rooms)):
        for j in xrange(len(rooms[i])):
            if rooms[i][j] == 0:
                visit(rooms, i, j)


def visit(rooms, i, j):
    queue = deque([(i, j)])
    while len(queue) > 0:
        i, j = queue.popleft()
        if i > 0 and rooms[i - 1][j] > rooms[i][j]:
            rooms[i - 1][j] = rooms[i][j] + 1
            queue.append((i - 1, j))
        if j > 0 and rooms[i][j - 1] > rooms[i][j]:
            rooms[i][j - 1] = rooms[i][j] + 1
            queue.append((i, j - 1))
        if i < len(rooms) - 1 and rooms[i + 1][j] > rooms[i][j]:
            rooms[i + 1][j] = rooms[i][j] + 1
            queue.append((i + 1, j))
        if j < len(rooms[i]) - 1 and rooms[i][j + 1] > rooms[i][j]:
            rooms[i][j + 1] = rooms[i][j] + 1
            queue.append((i, j + 1))


if __name__ == '__main__':
    INF = 2147483647
    rooms = [[INF,  -1,     0,      INF],       # [3,  -1,  0,  1]
             [INF,  INF,    INF,    -1],        # [2,   2,  1, -1]
             [INF,  -1,     INF,    -1],        # [1,  -1,  2, -1]
             [0,    -1,     INF,    INF]]       # [0,  -1,  3,  4]
    walls_and_gates(rooms)
    print rooms

