[tag] shortest path, BFS
- Has multiple targets, use all of them as starting point to be more efficient.
'''
add all 0 to queue and change all 1 to -1
for each element:
add 0 to queue
change 1 to -1 when appending.
change -1 to min distance after visted/pop
distance = 0
while queue:
for _ in range()
x y= pop
newx newy in 4 dirs
if valid and -1 append so it wont be covered again
change xy to distance also means visited
distance ++
'''
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
ROW, COL = len(mat), len(mat[0])
mat_q = deque()
directions = [(1,0), (-1, 0), (0,1), (0, -1)]
for i in range(ROW):
for j in range(COL):
if mat[i][j]:
mat[i][j] = -1
else:
mat_q.append((i, j))
distance = 0
while(mat_q):
cur_len = len(mat_q)
for i in range(cur_len):
x, y = mat_q.popleft()
for one_dir in directions:
new_x = x + one_dir[0]
new_y = y + one_dir[1]
if 0 <= new_x < ROW and 0 <= new_y < COL and mat[new_x][new_y] == -1:
mat_q.append((new_x, new_y))
mat[new_x][new_y] = distance + 1
distance += 1
return mat