python - 01 matrix - bfs


  • 0
    S
    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
                
                
            
    

Log in to reply
 

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