LeetCode #286: Walls and Gates

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 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.

For example, given the 2D grid:

INF -1 0 INF

INF INF INF -1

INF -1 INF -1

0 -1 INF INF

After running your function, the 2D grid should be:

3 -1 0 1

2 2 1 -1

1 -1 2 -1

0 -1 3 4

Solution:

• Start from the gates on the edges of the grids, and traverse the map with DFS or BFS.
• Modify the value of grids in-place.
• Time complexity: O(k*N), k is the number of gates on the edges
• Space complexity: O(N^2)

def mindistance(field):
    nrow = len(field); ncol = len(field[0])

    # left-boundary
    for i in range(nrow):
        if field[i][0] == 0:
            mindist_BFS(field, i, 0)

    # right-boundary
    for i in range(nrow):
        if field[i][ncol-1] == 0:
            mindist_BFS(field, i, ncol-1)

    # top-boundary
    for j in range(1,ncol-1):
        if field[0][j] == 0:
            mindist_BFS(field, 0, j)

    # bottom-boundary
    for j in range(1,ncol-1):
        if field[nrow-1][j] == 0:
            mindist_BFS(field, nrow-1, j)

    for x in field: print(x) 
    return 

def mindist_BFS(field, i0, j0):
    nrow = len(field); ncol = len(field[0])
    queue = [[i0,j0,0]]
    while len(queue)>0:
        loc = queue.pop(0)
        i=loc[0]; j=loc[1]
        if i-1>=0 and loc[2]+1<field[i-1][j]:
            field[i-1][j] = loc[2]+1
            queue.append([i-1,j,loc[2]+1])
        if i+1<nrow and loc[2]+1<field[i+1][j]:
            field[i+1][j] = loc[2]+1
            queue.append([i+1,j,loc[2]+1])
        if j-1>=0 and loc[2]+1<field[i][j-1]:
            field[i][j-1] = loc[2]+1
            queue.append([i,j-1,loc[2]+1])
        if j+1<ncol and loc[2]+1<field[i][j+1]:
            field[i][j+1] = loc[2]+1
            queue.append([i,j+1,loc[2]+1])
    return        

e = 2147483647
field= [[e, -1,  0,  e], 
        [e,  e,  e, -1], 
        [e, -1,  e, -1], 
        [0, -1,  e,  e]]

mindistance(field)