Python程式移除完全被水包圍的島嶼

假設我們有一個二進位制矩陣，其中 1 表示陸地，0 表示水。一個島嶼是由 1 組成的，並且被 0（水）或邊緣包圍。我們需要找到所有完全被水包圍的島嶼，並將它們修改為 0。我們知道，如果一個島嶼的所有鄰居（水平和垂直，而非對角線）都是 0（沒有鄰居是邊緣），則該島嶼被完全包圍。

因此，如果輸入如下所示：

1000
0110
0110
0110
0001

則輸出將是

1000
0000
0000
0000
0001

為了解決這個問題，我們將遵循以下步驟：

  • row := A 的行數

  • col := A 的列數

  • B := 一個與 A 大小相同且填充為 0 的矩陣

  • seen := 一個新的集合

  • 對於範圍從 0 到 row 的 i，執行：

    • 對於範圍從 0 到 col 的 j，執行：

      • 如果 i 和 j 超出矩陣範圍，則

        • 進行下一次迭代

      • 如果 (i, j) 已經被訪問過，則

        • 進行下一次迭代

      • 如果 A[i, j] 等於 0，則

        • 進行下一次迭代

      • d := 一個雙端佇列，包含一個元素 (i, j)

      • 當 d 不為空時，執行：

        • (x, y) := d 的左側元素，並從 d 中刪除

        • B[x, y] := 1

        • 對於 (x, y) 的每個鄰居 (x2, y2)，執行：

          • 如果 (x2, y2) 沒有被訪問過，則

            • 將 (x2, y2) 插入到 d 的末尾

            • 標記 (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]
]

更新於: 2020年12月22日

635 次瀏覽

開啟你的 職業生涯

完成課程獲得認證

立即開始
廣告