LeetCode-Python-542. 01マトリクス

1650 ワード

0と1からなる行列を与え,各要素から最も近い0までの距離を見つけた.
2つの隣接する要素間の距離は1です.
例1:入力:
0 0 0
0 1 0
0 0 0

出力:
0 0 0
0 1 0
0 0 0

例2:入力:
0 0 0
0 1 0
1 1 1

出力:
0 0 0
0 1 0
1 2 1

注意:
  • 所与の行列の要素個数は10000を超えない.
  • 所与の行列の少なくとも1つの要素は0である.
  • 行列の要素は、上、下、左、右の4つの方向にのみ隣接しています.

  • 考え方:
    すべての1から0の最短距離を探して、BFSを使います.
    from collections import deque
    class Solution(object):
        def updateMatrix(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[List[int]]
            """
            if not matrix or not matrix[0]:
                return matrix
            m, n = len(matrix), len(matrix[0])
            res = matrix[:]
            
            q = deque()
                   
            for i in range(m):
                for j in range(n):
                    if matrix[i][j] == 0:
                        q.append([[i, j], 0])
    
            dx = [1, -1, 0, 0]        
            dy = [0, 0, 1, -1]
            visited = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    
            while q:
                tmp, distance = q.popleft()
                x0, y0 = tmp[0], tmp[1]
    
                if matrix[x0][y0] == 1:
                    res[x0][y0] = distance
    
                for k in range(4):
                    x = x0 + dx[k]
                    y = y0 + dy[k]
    
                    if 0 <= x < m and 0 <= y < n and visited[x][y] != 1:
                        q.append([[x, y], distance + 1])
                        visited[x][y] = 1
            return res