Pythonですべてのセルに必要な操作の数を同じ色にカウントするプログラム

2次元行列Mがあるとします。各セルにその色を表す値が含まれ、同じ色の隣接するセル（上、下、左、右）がグループ化されます。ここで、1つのグループのすべてのセルをある色に設定する操作について考えてみます。次に、すべてのセルが同じ色になるように、必要な操作の最小数を最後に見つけます。また、色が変換されると、再度設定することはできません。

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

次に、出力は2になります。これは、グループを2で色として1に塗りつぶし、次に3を1で塗りつぶすことができるためです。

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

• 行列が空の場合、

  • 0を返す

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

• n：=行列の行数、m：=行列の列数

• i<0またはi>n-1またはj<0またはj>m-1の場合、

  • 戻る

• matrix [i、j]が-1と同じ場合、

  • 戻る

• matrix [i、j]がvalと同じ場合、

  • matrix [i、j]：=-1

  • dfs（i、j + 1、matrix、val）

  • dfs（i + 1、j、matrix、val）

  • dfs（i、j-1、matrix、val）

  • dfs（i-1、j、matrix、val）

• それ以外の場合

  • 戻る

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

• n：=行列の行数、m：=行列の列数

• d：=空のマップ

• 0からn-1の範囲のiの場合、実行

  • 0からm-1の範囲のjの場合、実行

  • val：=matrix [i、j]

  • valが-1と同じでない場合、

  • d [val]：=d [val] + 1

  • dfs（i、j、matrix、val）

• 値に基づいてfの辞書要素を並べ替える

• 安全：=lの最後の要素

• res：=0

• dのキー値ペアkとvごとに、実行します

  • kが安全と同じでない場合、

  • res：=res + v

• 解像度を返す

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

例

from collections import defaultdict
class Solution:
   def solve(self, matrix):
      if not matrix:
         return 0
      def dfs(i, j, matrix, val):
         n, m = len(matrix), len(matrix[0])
      if i < 0 or i > n - 1 or j < 0 or j > m - 1:
         return
      if matrix[i][j] == -1:
         return
      if matrix[i][j] == val:
         matrix[i][j] = -1
      dfs(i, j + 1, matrix, val)
      dfs(i + 1, j, matrix, val)
      dfs(i, j - 1, matrix, val)
      dfs(i - 1, j, matrix, val)
      else:
         return
      n, m = len(matrix), len(matrix[0])
      d = defaultdict(int)
   for i in range(n):
      for j in range(m):
         val = matrix[i][j]
   if val != -1:
      d[val] += 1
      dfs(i, j, matrix, val)
      l = sorted(d,key=lambda x: d[x])
      safe = l[-1]
      res = 0
   for k, v in d.items():
      if k != safe:
         res += v
   return res
ob = Solution()
matrix = [
   [2, 2, 2, 2],
   [1, 1, 1, 1],
   [2, 3, 2, 1]
]
print(ob.solve(matrix))

入力

matrix = [[2, 2, 2, 2],[1, 1, 1, 1],[2, 3, 2, 1]]

出力

2