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