Python程式：查詢無法離開的島嶼數量

假設我們有一個二進位制矩陣。其中1代表陸地，0代表水。從任何一塊陸地，我們可以上下左右移動，但不能對角線移動到另一個陸地單元格或移出矩陣。我們必須找到無法移出矩陣的陸地單元格的數量。

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

則輸出將為4，因為中間有4個陸地方格無法走出矩陣。

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

• q := 一個包含 (i, j) 對的列表，其中對於每一行 i 和列 j，matrix[i, j] 為陸地，i 和 j 是邊界索引
• idx := 0
• 對於q中的每個對 (x, y)，執行：
  • matrix[x, y] := 0
• 當 idx < q 的大小 時，執行：
  • x, y := q[idx]
  • 對於每個 (dx, dy) in [(-1, 0) ,(0, -1) ,(0, 1) ,(1, 0) ]，執行：
    • nx := x + dx
    • ny := y + dy
    • 如果 0 <= nx < 矩陣的行數 並且 0 <= ny < 矩陣[nx] 的列數 並且 matrix[nx, ny] 為 1，則：
      • matrix[nx, ny] := 0
      • 將 (nx, ny) 插入到 q 的末尾
  • idx := idx + 1
• 返回矩陣所有元素的總和

示例

讓我們看下面的實現來更好地理解：

def solve(matrix):
   q = [(i, j) for i in range(len(matrix)) for j in range(len(matrix[i])) if matrix[i][j] and (i == 0 or i == len(matrix) - 1 or j == 0 or j == len(matrix[i]) - 1)]
   idx = 0
   for x, y in q:
      matrix[x][y] = 0
   while idx < len(q):
      x, y = q[idx]
      for dx, dy in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
         nx, ny = x + dx, y + dy
         if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[nx]) and matrix[nx][ny]:
            matrix[nx][ny] = 0
            q.append((nx, ny))
      idx += 1
   return sum(sum(row) for row in matrix)

matrix = [
[0, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1]
]
print(solve(matrix))

輸入

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

輸出

4

Arnab Chakraborty

更新於：2021年10月18日

139 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習