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