01 Matrix (Leetcode 542)
Similar to Rotten Oranges
Problem Link: https://leetcode.com/problems/01-matrix/
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
m=len(matrix)
n=len(matrix[0])
visited=[[0 for i in range(n)] for j in range(m)]
ans=[[0 for i in range(n)] for j in range(m)]
q=[]
for i in range(m):
for j in range(n):
if(matrix[i][j]==0):
q.insert(0,[i,j,0])
visited[i][j]=1
while(len(q)>0):
i,j,dist=q.pop()
ans[i][j]=dist
if(i-1>=0 and visited[i-1][j]==0 and matrix[i-1][j]==1):
visited[i-1][j]=1
q.insert(0,[i-1,j,dist+1])
if(j-1>=0 and visited[i][j-1]==0 and matrix[i][j-1]==1):
visited[i][j-1]=1
q.insert(0,[i,j-1,dist+1])
if(i+1<m and visited[i+1][j]==0 and matrix[i+1][j]==1):
visited[i+1][j]=1
q.insert(0,[i+1,j,dist+1])
if(j+1<n and visited[i][j+1]==0 and matrix[i][j+1]==1):
visited[i][j+1]=1
q.insert(0,[i,j+1,dist+1])
return ans
Last updated