Pythonの2つのマップで重複する島の数をカウントするプログラム

2つのバイナリ行列mat1とmat2があるとします。ここで、1は土地を表し、0は水を表します。水に囲まれた1（土地）のグループがある場合、島と呼ばれます。 mat1とmat2の両方にまったく同じ座標で存在する島の数を見つける必要があります。

したがって、入力がmat1 =

そしてmat2=

重なり合う島は2であるため、出力は2になります。

したがって、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]いずれか1つがゼロ以外）の場合、
  • mark（i-1、j）
• jがゼロ以外で（mat1 [i、j-1]またはmat2 [i、j-1]いずれか1つがゼロ以外）の場合、
  • mark（i、j-1）
• j
• mark（i、j + 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