Pythonで水から最も遠い土地を見つけるプログラム

0が水を表し、1が土地を表すバイナリ行列があるとします。ここで、マンハッタンの水からの距離が最も長い土地を見つけて、最終的にその距離を返す必要があります。

したがって、入力が次のような場合

[0,0]セルのマンハッタン距離は水から3であるため、出力は3になります。

これを解決するには、次の手順に従います-

• Aが空の場合、
  • 0を返す
• R：=行列の行数、C：=行列の列数
• 距離：=次数R x Cの行列で、0で埋めます
• q：=いくつかのペア（r、c）を持つ両端キュー。rとcは行列の行と列のインデックスで、matrix [r、c]は0です。
• qのサイズが0またはR*Cである場合、
  • 戻り値-1
• qが空でない間は、
  • （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：=各行の最大要素を含むリスト
• 最大解像度を返す

例（Python）

理解を深めるために、次の実装を見てみましょう-

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