极客教程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的所有元素的和
示例
让我们看以下实现以获得更好的理解 –