Python程序：计算两张地图中重叠岛屿的数量

假设我们有两个二进制矩阵mat1和mat2。其中1代表陆地，0代表水，如果有一组1（陆地）被水包围，则称为岛屿。我们必须找到在mat1和mat2中完全相同坐标处存在的岛屿数量。

因此，如果输入类似于mat1 =

而mat2 =

则输出将为2，因为重叠的岛屿是：

所以有两个重叠的岛屿。

为了解决这个问题，我们将遵循以下步骤：

• 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)
• 在主方法中，执行以下操作：
• 对于范围从0到r - 1的i，执行
  • 对于范围从0到c - 1的j，执行
    • 如果mat1[i, j]与mat2[i, j]不同，则
      • mark(i, j)
• islands := 0
• 对于范围从0到r - 1的i，执行
  • 对于范围从0到c - 1的j，执行
    • 如果mat1[i, j]非零，则
      • islands := islands + 1
      • mark(i, j)
• 返回islands

示例

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

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

Arnab Chakraborty

更新于：2021年10月18日

浏览量：126

开启你的职业生涯

完成课程获得认证

开始学习