难度: Hard
给你一个 m x n 的二进制矩阵 mat。每一步，你可以选择一个单元格并将它反转（反转表示 0 变 1 ，1 变 0 ）。如果存在和它相邻的单元格，那么这些相邻的单元格也会被反转。相邻的两个单元格共享同一条边。
请你返回将矩阵 mat 转化为全零矩阵的最少反转次数，如果无法转化为全零矩阵，请返回 -1 。
二进制矩阵 的每一个格子要么是 0 要么是 1 。
全零矩阵 是所有格子都为 0 的矩阵。
示例 1：
输入：mat = [[0,0],[0,1]] 输出：3 解释：一个可能的解是反转 (1, 0)，然后 (0, 1) ，最后是 (1, 1) 。
示例 2：
输入：mat = [[0]] 输出：0 解释：给出的矩阵是全零矩阵，所以你不需要改变它。
示例 3：
输入：mat = [[1,0,0],[1,0,0]] 输出：-1 解释：该矩阵无法转变成全零矩阵
提示：
m == mat.lengthn == mat[0].length1 <= m <= 31 <= n <= 3mat[i][j] 是 0 或 1 。运行时间: 36 ms
内存: 16.1 MB
class Solution:
def minFlips(self, mat: List[List[int]]) -> int:
n,m=len(mat),len(mat[0])
temp=[[1,0],[-1,0],[0,1],[0,-1]]
def reverse(x,y):
mat[x][y]=1-mat[x][y]
for dx,dy in temp:
nx,ny=x+dx,y+dy
if 0<=nx<=n-1 and 0<=ny<=m-1:
mat[nx][ny]=1-mat[nx][ny]
def dfs(x,y):
if x==n:
if all(i==0 for row in mat for i in row):return 0
return inf
nx =x+1 if y==m-1 else x
ny=y+1 if y<m-1 else 0
ans=dfs(nx,ny)
reverse(x,y)
ans=min(ans,dfs(nx,ny)+1)
reverse(x,y)
return ans
ans=dfs(0,0)
return ans if ans!=inf else -1
这个题解采用了深度优先搜索（DFS）来解决问题，通过尝试每个单元格的不同状态（反转或不反转）来寻找解决方案。函数 `reverse(x, y)` 负责反转指定单元格及其四周相邻的单元格。`dfs(x, y)` 函数尝试当前位置的所有可能性，并递归地处理矩阵的下一个位置。如果矩阵的每个元素都能通过一系列反转变为0，则记录并返回反转次数。算法尝试每个位置的两种状态（反转或不反转），并通过递归来尝试所有可能的状态组合，直至找到将矩阵转换成全零矩阵的最少反转次数或确定无法转换。如果能找到，返回最少反转次数；否则，返回-1。
时间复杂度: O(2^k)，其中k为矩阵中的单元格数
空间复杂度: O(k)，其中k为矩阵中的单元格数
class Solution:
def minFlips(self, mat: List[List[int]]) -> int:
n, m = len(mat), len(mat[0])
temp = [[1, 0], [-1, 0], [0, 1], [0, -1]]
def reverse(x, y):
# 反转指定单元格及其邻居
mat[x][y] = 1 - mat[x][y]
for dx, dy in temp:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < m:
mat[nx][ny] = 1 - mat[nx][ny]
def dfs(x, y):
# 递归尝试矩阵所有位置的反转状态
if x == n:
if all(i == 0 for row in mat for i in row):
return 0
return float('inf')
nx = x + 1 if y == m - 1 else x
ny = y + 1 if y < m - 1 else 0
ans = dfs(nx, ny)
reverse(x, y)
ans = min(ans, dfs(nx, ny) + 1)
reverse(x, y)
return ans
ans = dfs(0, 0)
return ans if ans != float('inf') else -1
在DFS递归函数中执行两次`reverse(x, y)`操作是为了恢复矩阵到原始状态，以便继续探索其他可能的状态组合。这种方法称为“回溯”。首次调用`reverse(x, y)`是为了探索如果反转当前单元格（及其相邻单元格）后能否导致整个矩阵变为全零状态。第二次调用`reverse(x, y)`是为了将这些单元格恢复到初始状态，从而不影响后续的递归搜索。这种做法允许算法在不修改原始输入的情况下探索所有可能的状态，是一种常用的深度优先搜索技巧。
题解中的处理方式表明，当递归到矩阵的最后一个位置并发现所有单元格已经是0时，直接返回0。这并不意味着算法需要矩阵初始就是全零状态；实际上，这是指在递归过程中如果任何一个递归路径能够将矩阵转化为全零矩阵，该路径的反转次数将被考虑为最终结果。这里返回0是因为函数设计是以反转次数进行累计计算，当找到全零矩阵时，说明从当前递归开始到最终状态不需要再进行额外反转，因此从这一点返回的是0，代表着这一分支的额外反转次数。这种处理方式是合理的，因为它正确地计算了达到全零状态所需的最少反转次数。
在使用DFS方法时，如果尝试了所有可能的反转组合后仍然无法使矩阵中的所有单元格都变为0，算法会确定矩阵不能被转换成全零矩阵。这通常发生在矩阵的大小或初始状态导致某些单元格无法通过任何反转操作达到全零状态。例如，如果矩阵的某些特定配置或者它的奇偶性导致无法通过相邻的反转操作使得所有单元格均为0，DFS搜索将探索所有可能的反转组合并最终返回float('inf')，表示不可能达成目标。在这种情况下，算法会最终返回-1，表示无解状态。