Pythonで水に完全に囲まれているすべての島を削除するプログラム

1が土地を表し、0が水を表すバイナリ行列があるとします。また、島は1のグループであり、0（水）またはエッジで囲まれています。完全に水に囲まれているすべての島を見つけて、それらを0に変更する必要があります。私たちが知っているように、すべての隣人（斜めではなく水平と垂直）が0の場合（隣人のどれもエッジではない）、島は水に囲まれて完成します。

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

その場合、出力は次のようになります

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

• 行：=Aの行数

• col：=Aの列数

• B：=サイズAの行列で、0で埋める

• 見た：=新しいセット

• 0から行までの範囲のiの場合、実行

  • 0からcolの範囲のjについては、次のようにします

    • iとjが行列の範囲内にない場合、

      • 次のイテレーションに行く

    • （i、j）が見られる場合、

      • 次のイテレーションに行く

    • A [i、j]が0と同じ場合、

      • 次のイテレーションに行く

    • d：=1つの要素（i、j）を持つ両端キュー

    • dは空ではありませんが、実行してください

      • （x、y）：=dの左側の要素、およびdから削除

      • B [x、y]：=1

      • （x、y）の各ネイバー（x2、y2）に対して、実行

        • （x2、y2）が表示されない場合、

          • dの最後に（x2、y2）を挿入します

          • 見られるように（x2、y2）をマークします

• Bを返す

例

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

from collections import deque
class Solution:
   def solve(self, A):
      row = len(A)
      col = len(A[0])
      B = [[0 for _ in range(col)] for _ in range(row)]
      seen = set()
      def nei(i, j):
         if i + 1 < row and A[i + 1][j]:
            yield (i + 1, j)
         if j + 1 < col and A[i][j + 1]:
            yield (i, j + 1)
         if i - 1 >= 0 and A[i - 1][j]:
            yield (i - 1, j)
         if j - 1 >= 0 and A[i][j - 1]:
            yield (i, j - 1)
         for i in range(row):
            for j in range(col):
               if i not in (0, row - 1) and j not in (0, col - 1):
                  continue
               if (i, j) in seen:
                  continue
               if A[i][j] == 0:
                  continue
               d = deque([(i, j)])
               while d:
                  x, y = d.popleft()
                  B[x][y] = 1
                  for x2, y2 in nei(x, y):
                     if (x2, y2) not in seen:
                        d.append((x2, y2))
                        seen.add((x2, y2))
         return B
ob = Solution()
matrix = [
   [1, 0, 0, 0],
   [0, 1, 1, 0],
   [0, 1, 1, 0],
   [0, 1, 1, 0],
   [0, 0, 0, 1],
]
print(ob.solve(matrix))

入力

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

出力

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