title
给你一个大小为 m x n 的二维矩形 grid 。每次 操作 中，你可以将 任一 格子的值修改为 任意 非负整数。完成所有操作后，你需要确保每个格子 grid[i][j] 的值满足：
- 如果下面相邻格子存在的话，它们的值相等，也就是
grid[i][j] == grid[i + 1][j]（如果存在）。 - 如果右边相邻格子存在的话，它们的值不相等，也就是
grid[i][j] != grid[i][j + 1]（如果存在）。
请你返回需要的 最少 操作数目。
示例 1：
输入：grid = [[1,0,2],[1,0,2]]
输出：0
解释：
矩阵中所有格子已经满足要求。
示例 2：
输入：grid = [[1,1,1],[0,0,0]]
输出：3
解释：
将矩阵变成 [[1,0,1],[1,0,1]] ，它满足所有要求，需要 3 次操作：
- 将
grid[1][0]变为 1 。 - 将
grid[0][1]变为 0 。 - 将
grid[1][2]变为 1 。
示例 3：
输入：grid = [[1],[2],[3]]
输出：2
解释：
这个矩阵只有一列，我们可以通过 2 次操作将所有格子里的值变为 1 。
提示：
1 <= n, m <= 10000 <= grid[i][j] <= 9
solution
class Solution:
def minimumOperations(self, grid: List[List[int]]) -> int:
grid = list(zip(*grid[::-1]))
m, n = len(grid), len(grid[0])
d = []
for i in range(m):
counter = collections.Counter(grid[i][:])
d.append(counter)
# print(d)
import functools
@functools.lru_cache(None)
def dfs(i, v):
if i == -1:
return 0
counter = d[i]
res = float('inf')
for j in range(10):
if j == v:
continue
t = dfs(i - 1, j) + n - counter[j]
res = min(res, t)
return res
ans = dfs(m - 1, -1)
return ans