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