Pythonの特定の行列からいくつかの異なる島の形状を見つけるプログラム

2次元のバイナリ行列があるとすると、与えられた行列内の個別の島の数を見つける必要があります。ここで、1は土地を表し、0は水を表します。したがって、島は1のセットであり、その周囲は水に囲まれています。ここでは、形が異なる場合、2つの島がユニークです。

したがって、入力が次のような場合

その場合、出力は4になります（異なる島は異なる色になります）。

これを解決するには、次の手順に従います-

• 関数dfs（）を定義します。これにはi、j、k、lが必要です

• mat [i、j]：=0

• 形状の最後にペア（i − k、j − l）を挿入します

• i +1<マットの行数およびmat[i+ 1、j]が1の場合、

  • dfs（i + 1、j、k、l）

• j + 1

  • dfs（i、j + 1、k、l）

• i − 1> =0で、mat [i − 1、j]が1の場合、

  • dfs（i − 1、j、k、l）

• j − 1> =0で、mat [i、j − 1]が1の場合、

  • dfs（i、j − 1、k、l）

• メインの方法から、次のようにします-

• cnt：=0

• 形状：=新しいセット

• 0からマットの行数までの範囲のiの場合、実行します

  • 0からマットの列数までの範囲のjについては、次のようにします

    • mat [i、j]が1の場合、

      • shape：=新しいリスト

      • dfs（i、j、i、j）

      • 形が形になっていない場合は

        • cnt：=cnt + 1

      • 図形を図形に挿入する

• cntを返す

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, mat):
      def dfs(i, j, k, l):
         mat[i][j] = 0
         shape.append((i − k, j − l))
      if i + 1 < len(mat) and mat[i + 1][j]:
         dfs(i + 1, j, k, l)
      if j + 1 < len(mat[0]) and mat[i][j + 1]:
         dfs(i, j + 1, k, l)
      if i − 1 >= 0 and mat[i − 1][j]:
         dfs(i − 1, j, k, l)
      if j − 1 >= 0 and mat[i][j − 1]:
         dfs(i, j − 1, k, l)
   cnt = 0
   shapes = set()
      for i in range(len(mat)):
         for j in range(len(mat[0])):
            if mat[i][j]:
               shape = []
               dfs(i, j, i, j)
               shape = tuple(shape)
               if shape not in shapes:
                  cnt += 1
                  shapes.add(shape)
      return cnt
ob = Solution()
matrix = [
   [1, 0, 0, 0, 0],
   [1, 0, 1, 0, 1],
   [0, 1, 1, 0, 1],
   [0, 0, 1, 0, 0],
   [1, 0, 0, 0, 0],
   [1, 1, 0, 1, 1]
]
print(ob.solve(matrix))

入力

[
   [1, 0, 0, 0, 0],
   [1, 0, 1, 0, 1],
   [0, 1, 1, 0, 1],
   [0, 0, 1, 0, 0],
   [1, 0, 0, 0, 0],
   [1, 1, 0, 1, 1]
]

出力

4