# python - 01 matrix - bfs

• ``````class Solution(object):
def updateMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
INT_MAX = pow(2,31)
rows = len(matrix)
if not rows:
return []

cols = len(matrix[0])

dist = [[0 for c in range(cols)] for r in range(rows)]
queue = []

for r in range(rows):
for c in range(cols):
if matrix[r][c]: # == 1
dist[r][c] = INT_MAX
queue.append((r,c))

length = len(queue)
while length:
cur = queue.pop()
length -= 1
cur_r, cur_c = cur[0], cur[1]

if cur_r < 0 or cur_r > rows - 1 or cur_c < 0 or cur_c > cols - 1:
continue

cur_d = dist[cur_r][cur_c]

top = (1+dist[cur_r-1][cur_c]) if cur_r else INT_MAX
down = (1+dist[cur_r+1][cur_c]) if cur_r < rows-1 else INT_MAX
left = (1+dist[cur_r][cur_c-1]) if cur_c else INT_MAX
right = (1+dist[cur_r][cur_c+1]) if cur_c < cols-1 else INT_MAX

min_d = min(top,down,left,right)

if min_d < cur_d:
dist[cur_r][cur_c] = min_d

# append the neighbors
nh_top = (cur_r-1, cur_c)
nh_down = (cur_r+1, cur_c)
nh_left = (cur_r, cur_c-1)
nh_right = (cur_r, cur_c+1)
queue.append(nh_top)
queue.append(nh_down)
queue.append(nh_left)
queue.append(nh_right)
length += 4

return dist

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.