Python程序：计算将所有单元格颜色变为相同的所需操作次数

假设我们有一个二维矩阵 M。每个单元格包含一个表示其颜色的值，并且具有相同颜色的相邻单元格（上、下、左、右）需要组合在一起。现在，考虑一个操作，我们将一个组中的所有单元格设置为某种颜色。然后最终找到使每个单元格都具有相同颜色的所需的最少操作次数。当颜色发生转换时，不能再次设置。

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

则输出为 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

Arnab Chakraborty

更新于: 2020年10月5日

167 次查看

开启你的职业生涯

完成课程后获得认证

开始学习