Python程序：查找无法离开的岛屿数量

假设我们有一个二进制矩阵。其中1代表陆地，0代表水。从任何一块陆地，我们可以上下左右移动，但不能对角线移动到另一个陆地单元格或移出矩阵。我们必须找到无法移出矩阵的陆地单元格的数量。

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

0001
0110
0110
0001

则输出将为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

更新于：2021年10月18日

139 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告