在Python中编写用于计算两张地图中重叠的岛屿数量的程序
假设有两个二元矩阵mat1和mat2。如果有一组1(陆地)被水包围,则称之为岛屿,这是1代表陆地,0代表水。我们必须找出在mat1和mat2中恰好相同的坐标处存在的岛屿数量。
因此,如果输入是 mat1 =
1 | 0 | 1 |
---|---|---|
1 | 0 | 0 |
1 | 0 | 0 |
和 mat2 =
1 | 0 | 1 |
---|---|---|
1 | 0 | 0 |
1 | 0 | 1 |
那么输出将是2,因为重叠的岛屿为,
1 | 0 | 1 |
---|---|---|
1 | 0 | 0 |
1 | 0 | 1 |
所以有两个重叠的岛屿。
要解决此问题,我们将执行以下步骤-
- r:= mat1的行数
- c:= mat1的列数
- last_row:= r-1
- last_col := c-1
- 定义一个函数mark() 。这将需要 i,j
- mat1[i,j]:= 0
- mat2[i,j]: =0
- 如果i不为零,且(mat1[i-1,j]或mat2[i-1,j]任一不为零),则
- mark(i-1,j)
- 如果j不为零,且(mat1[i,j – 1]或mat2[i,j – 1]任一不为零),则
- mark(i,j-1)
- 如果j< last_col,并且(mat1 [i,j + 1]或mat2 [i,j + 1]任一不为零),则
- mark(i,j+1)
- 如果i < last_row,并且(mat1[i + 1,j]或mat2 [i+1,j]任一不为零),则
- mark(i + 1, j)
- 从main方法开始,执行以下操作-
- 对于i在0到r-1范围内,执行以下操作-
- 对于j在0到c-1范围内,执行以下操作-
- 如果mat1 [i, j]不同于 mat2[i,j],则
- mark(i, j)
- 对于j在0到c-1范围内,执行以下操作-
- 岛屿: = 0
- 对于i在0到r-1的范围内,执行以下操作-
- 对于j在0到c-1的范围内,执行以下操作-
- 如果mat1[i,j]不为零,则
- island:=岛+1
- mark(i,j)
- 对于j在0到c-1的范围内,执行以下操作-
- 返回岛屿
示例
让我们看下面的实现以更好地理解-
def solve(mat1, mat2):
r = len(mat1)
c = len(mat1[0])
last_row = r - 1
last_col = c - 1
def mark(i, j):
mat1[i][j] = mat2[i][j] = 0
if i and (mat1[i - 1][j] or mat2[i - 1][j]):
mark(i - 1, j)
if j and (mat1[i][j - 1] or mat2[i][j - 1]):
mark(i, j - 1)
if j < last_col and (mat1[i][j + 1] or mat2[i][j + 1]):
mark(i, j + 1)
if i < last_row and (mat1[i + 1][j] or mat2[i + 1][j]):
mark(i + 1, j)
for i in range(r):
for j in range(c):
if mat1[i][j] != mat2[i][j]:
mark(i, j)
islands = 0
for i in range(r):
for j in range(c):
if mat1[i][j]:
islands += 1
mark(i, j)
return islands
mat1 = [
[1, 0, 1],
[1, 0, 0],
[1, 0, 1]
]
mat2 = [
[1, 0, 1],
[1, 0, 0],
[1, 0, 0]
]
print(solve(mat1, mat2))
输入
[
[1, 0, 1],
[1, 0, 0],
[1, 0, 1]
]
[
[1, 0, 1],
[1, 0, 0],
[1, 0, 0]
]
输出
2