Python中查找不能离开的岛屿数量的程序

Python中查找不能离开的岛屿数量的程序

假设我们有一个二进制矩阵。这里 1 代表陆地,0 代表水域。从任何陆地出发,我们可以向上、向下、向左或向右移动,但不能对角线地走到另一个陆地单元格或走出矩阵。我们必须找出从哪些陆地单元格无法走出矩阵,即查找不能离开的陆地单元格数量。

那么,如果输入如下:

0 0 0 1
0 1 1 0
0 1 1 0
0 0 0 1

则输出将为4,因为在中间有4个不能走出矩阵的陆地方块。

为了解决这个问题,我们将遵循以下步骤:

  • q := 一个包含二元组(i, j)的列表,其中i和j都是边缘索引,当 matrix[i, j] 是陆地时
  • idx := 0
  • 对于q中的每个二元组(x, y),执行以下操作:
    • matrix[x, y] := 0
  • while idx < q的长度,执行以下操作:
    • x, y := q[idx]
    • 对于[(-1, 0),(0, -1),(0, 1),(1, 0)]中的每个(dx, dy),执行以下操作:
      • nx := x + dx
      • ny := y + dy
      • 如果0 <= nx < matrix的行数,且0 <= ny < matrix[nx]的列数,并且 matrix[nx, ny] 是 1,则
      • matrix[nx, ny] := 0
      • 将(nx, ny)插入到q的末尾
    • idx := idx + 1
  • 返回matrix的所有元素的和

示例

让我们看以下实现以获得更好的理解 –

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程