用 Python 编写一个程序，计算将所有单元格变成相同颜色所需的操作次数
假设我们有一个二维矩阵 M。现在每个单元格包含一个代表其颜色的值，并且相邻的单元格(顶部、底部、左侧、右侧)具有相同的颜色，将被分组在一起。现在，考虑一个操作，我们将一个组中的所有单元格设置为某种颜色。然后最终找到使每个单元格具有相同颜色所需的最少操作次数。而且当颜色变换后，就不能再设置了。
所以，如果输入如下
| 2 | 2 | 2 | 2 |
| 1 | 1 | 1 | |
| 2 | 3 | 2 | 1 |
那么输出将是2，因为我们可以将颜色为2的组填充为1，然后将颜色为1的组填充为3。
为了解决这个问题，我们将遵循以下步骤−
如果矩阵为空，则
返回 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 := 空映射
对于范围为 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 的字典元素进行排序
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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
