在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)
• 岛屿: = 0
• 对于i在0到r-1的范围内，执行以下操作-
  • 对于j在0到c-1的范围内，执行以下操作-
    • 如果mat1[i，j]不为零，则
    • island：=岛+1
    • mark(i，j)
• 返回岛屿

示例

让我们看下面的实现以更好地理解-

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