Pythonで1つのウォーターセルをランドセルに変更した後、最大の島を見つけるプログラム

1が土地を表し、0が水を表すバイナリ行列があるとします。そして島は水に囲まれた1のグループです。最大の島の大きさを見つけなければなりません。最大で1つのウォーターセルをランドセルに変更できます。

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

その場合、出力は7になります。これは、1つの水セルを着陸させて2つの島を接続できるためです。したがって、最終的な行列は次のようになります-

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

• R：=マットの行数、C：=マットの列数

• 質量：=新しいマップ

• id：=555

• 関数floodfill（）を定義します。これにはr、c、idが必要です

• rとcが行列の範囲内にあり、mat [r、c]が1の場合、

  • mat [r、c]：=id

  • mass [id]：=mass [id] + 1

  • [（r + 1、c）、（r − 1、c）、（r、c + 1）、（r、c − 1）]の各ペア（r2、c2）について、実行

    • Floodfill（r2、c2、id）

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

• 0からRの範囲のrについては、次のようにします

  • 0からCの範囲のcについては、次のようにします

    • mat [r、c]が1と同じ場合、

      • id：=id + 1

      • mass [id]：=0

      • Floodfill（r、c、id）

• ans：=最大（質量と1のすべての値）

• 0からR− 1の範囲のrの場合、実行

  • 0からC− 1の範囲のcの場合、実行

    • mat [r、c]が0と同じでない場合、

      • 次のイテレーションに行く

    • island_set：=新しいセット

    • [（r + 1、c）、（r − 1、c）、（r、c + 1）、（r、c − 1）]の各ペア（r2、c2）について、実行

      • r2とc2がmatの範囲内にあり、mat [r2、c2]が1の場合、

        • mat [r2、c2]をisland_set

          に追加します

      • ans：=ansの最大値と（1+各島のすべてのmass[island]の合計inisland_set）

• ansを返す

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

例

class Solution:
   def solve(self, mat):
      R, C = len(mat), len(mat[0])
      mass = {}
      id = 555
      def floodfill(r, c, id):
         nonlocal R, C, mat, mass
         if 0 <= r < R and 0 <= c < C and mat[r][c] == 1:
            mat[r][c] = id
            mass[id] += 1
            for r2, c2 in [(r + 1, c), (r − 1, c), (r, c + 1),
               (r, c − 1)]:
               floodfill(r2, c2, id)
                  for r in range(R):
      for c in range(C):
         if mat[r][c] == 1:
            id += 1
            mass[id] = 0
            floodfill(r, c, id)
      ans = max([val for val in mass.values()] + [1])
      for r in range(R):
         for c in range(C):
            if mat[r][c] != 0:
               continue
            island_set = set()
            for r2, c2 in [(r + 1, c), (r − 1, c), (r, c + 1),(r, c − 1)]:
               if 0 <= r2 < R and 0 <= c2 < C and mat[r2][c2]:
                  island_set.add(mat[r2][c2])
               ans = max(ans, 1 + sum([mass[island] for island in island_set]))
         return ans
ob = Solution()
matrix = [
   [1, 0, 1],
   [0, 0, 0],
   [1, 1, 0],
   [1, 1, 1]
]
print(ob.solve(matrix))

入力

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

出力

7