Python에서 각 셀이 가장 가까운 0에서 맨해튼 거리를 유지하는 행렬을 생성하는 프로그램

이진 행렬이 있다고 가정합니다. 우리는 동일한 행렬을 찾아야 하지만 각 셀의 값은 가장 가까운 0에 대한 맨해튼 거리가 될 것입니다. 우리는 행렬에 적어도 하나의 0이 있다고 가정할 수 있습니다.

따라서 입력이 다음과 같으면

그러면 출력은

왼쪽 하단 셀만 2에서 가장 가까운 0까지의 거리를 갖기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• m :=행렬의 행 크기, n :=행렬의 열 크기
• 0~m 범위의 y에 대해
  • 0에서 n 사이의 x에 대해
    • 행렬[y, x]가 0이 아니면
      • 행렬[y, x] :=무한대
• 0~m 범위의 y에 대해
  • 0에서 n 사이의 x에 대해
    • y가 0이 아니면
      • 행렬[y, x] =행렬[y, x] 및 행렬[y - 1, x] + 1의 최소값
    • x가 0이 아니면
      • 행렬[y, x] =행렬[y, x] 및 행렬[y, x - 1] + 1의 최소값
• m - 1 ~ 0 범위의 y에 대해 1 감소, do
  • n - 1에서 0 사이의 x에 대해 1 감소, do
    • y + 1
    • 행렬[y, x] =행렬[y, x] 및 행렬[y + 1, x] + 1의 최소값
  • x + 1
  • 행렬[y, x] =행렬[y, x] 및 행렬[y, x + 1] + 1의 최소값

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

import math
class Solution:
   def solve(self, matrix):
      m, n = len(matrix), len(matrix[0])
      for y in range(m):
         for x in range(n):
            if matrix[y][x]:
               matrix[y][x] = math.inf
      for y in range(m):
         for x in range(n):
            if y:
               matrix[y][x] = min(matrix[y][x], matrix[y - 1][x] + 1)
            if x:
               matrix[y][x] = min(matrix[y][x], matrix[y][x - 1] + 1)
      for y in range(m - 1, -1, -1):
         for x in range(n - 1, -1, -1):
            if y + 1 < m:
               matrix[y][x] = min(matrix[y][x], matrix[y + 1][x] + 1)
            if x + 1 < n:
               matrix[y][x] = min(matrix[y][x], matrix[y][x + 1] + 1)
      return matrix
ob = Solution()
matrix = [ [1, 0, 1], [1, 0, 1], [1, 1, 0] ]
print(ob.solve(matrix))

입력

[[1, 0, 1],
[1, 0, 1],
[1, 1, 0] ]

출력

[[1, 0, 1], [1, 0, 1], [2, 1, 0]]