Python程式：計算將所有單元格顏色變為相同的所需操作次數

假設我們有一個二維矩陣 M。每個單元格包含一個表示其顏色的值，並且具有相同顏色的相鄰單元格（上、下、左、右）需要組合在一起。現在，考慮一個操作，我們將一個組中的所有單元格設定為某種顏色。然後最終找到使每個單元格都具有相同顏色的所需的最少操作次數。當顏色發生轉換時，不能再次設定。

因此，如果輸入如下所示：

2
2
2
2
1
1
1
1
2
3
2
1

則輸出為 2，因為我們可以將顏色為 2 的組填充為 1，然後將 3 填充為 1。

為了解決這個問題，我們將遵循以下步驟：

  • 如果矩陣為空，則

    • 返回 0

  • 定義一個函式 dfs()。它將接收 i、j、矩陣、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 := 空對映

  • 對於 i 的範圍從 0 到 n-1，執行

    • 對於 j 的範圍從 0 到 m-1，執行

    • val := matrix[i, j]

    • 如果 val 與 -1 不相同，則

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

    • dfs(i, j, matrix, val)

  • 根據其值對字典元素 f 進行排序

  • safe := l 的最後一個元素

  • res := 0

  • 對於 d 的每個鍵值對 k 和 v，執行

    • 如果 k 與 safe 不相同，則

    • res := res + v

  • 返回 res

讓我們檢視以下實現以更好地理解：

示例

 現場演示

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

更新於: 2020年10月5日

167 次檢視

開啟你的職業生涯

完成課程後獲得認證

開始學習
廣告