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

開啟你的職業生涯

完成課程獲得認證

開始學習