파이썬에서 물에서 가장 먼 땅을 찾는 프로그램

0이 물을 나타내고 1이 땅을 나타내는 이진 행렬이 있다고 가정합니다. 이제 우리는 물에서 맨하탄 거리가 가장 긴 땅을 찾아 최종적으로 거리를 반환해야 합니다.

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

[0,0] 셀의 맨해튼 거리가 물에서 3이므로 출력은 3이 됩니다.

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

• A가 비어 있으면
  • 0을 반환
• R :=행렬의 행 개수, C :=행렬의 열 개수
• 거리:=R x C 차수의 행렬이고 0으로 채워짐
• q :=일부 쌍(r, c)이 있는 이중 종료 큐(여기서 r 및 c는 행렬[r, c]가 0인 행렬의 행 및 열 인덱스임)
• q의 크기가 위더 0 또는 R * C이면
  • 반환 -1
• q가 비어 있지 않은 동안 do
  • (r, c) :=q의 왼쪽 요소, q에서 제거
  • [(r - 1, c) ,(r + 1, c) ,(r, c + 1) ,(r, c - 1) ]의 각 쌍(x, y)에 대해, do
    • x와 y가 행렬의 범위에 있고 A[x, y]가 1이면
      • A[x, y] :=0
      • 거리[x, y] :=거리[r, c] + 1
      • q 끝에 (x, y) 삽입
• res :=각 행의 최대 요소를 포함하는 목록
• 최대 res를 반환

예제(파이썬)

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

from collections import deque
class Solution:
   def solve(self, A):
      if not A:
         return 0
      R, C = len(A), len(A[0])
      distance = [[0] * C for _ in range(R)]
      q = deque((r, c) for r in range(R) for c in range(C) if not A[r][c])
      if len(q) in (0, R * C):
         return -1
      while q:
         r, c = q.popleft()
         for x, y in [(r - 1, c), (r + 1, c), (r, c + 1), (r, c - 1)]:
            if 0 <= x < R and 0 <= y < C and A[x][y]:
               A[x][y] = 0
               distance[x][y] = distance[r][c] + 1
               q.append((x, y))
      return max(max(row) for row in distance)
ob = Solution()
matrix = [
   [1, 1, 1, 1],
   [1, 1, 0, 1],
   [1, 1, 1, 1],
   [0, 0, 1, 1]
]
print(ob.solve(matrix))

입력

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

출력

3