队列中存储 $(state, steps)$ 。
$state = 0$ 时直接返回 $0$ 。
对于当前状态 $state$ $s t a t e$ ，尝试对每个格子 $(i, j)$ $(i, j)$ 进行反转：
- 计算反转后的新状态 $next\_state$ ：将 $(i, j)$ 及其上下左右邻格的对应位取反。
- 取反操作用异或实现：构造一个掩码 $mask$ ，要反转的位为 $1$ ，其余位为 $0$ ， $next\_state = state \oplus mask$ 。
- 如果 $next\_state$ 未访问过，入队并标记。

第 3 步：队列为空时返回 $-1$ 。

4. 结合示例走一遍

以 $1 \times 2$ 矩阵 $[[1, 0]]$ 为例：

初始状态：二进制 01（假设第 $0$ 位是 $(0,0)$ ，第 $1$ 位是 $(0,1)$ ），十进制 $1$ 。

第 0 层: state=1 (二进制 01)
  反转 (0,0): 影响 (0,0) 和 (0,1) → 掩码 11 (3) → state⊕3=2 (二进制 10)
  反转 (0,1): 影响 (0,0) 和 (0,1) → 掩码 11 (3) → state⊕3=2 (二进制 10)

第 1 层: state=2 (二进制 10)
  反转 (0,0): 影响 (0,0) 和 (0,1) → 掩码 11 (3) → state⊕3=1 (二进制 01) 已访问
  反转 (0,1): 影响 (0,0) 和 (0,1) → 掩码 11 (3) → state⊕3=1 (二进制 01) 已访问
  
队列为空，返回 -1。

这个例子说明 $[[1,0]]$ 无法变为全 $0$ 。

换个例子： $[[0,1],[1,0]]$ （ $2 \times 2$ ）：

初始状态：二进制 0110（位 $0$ =0, 位 $1$ =1, 位 $2$ =1, 位 $3$ =0），十进制 $6$ 。

反转 $(0,1)$ （影响 $(0,0),(0,1),(1,1)$ ）：

掩码：位 $0$ （ $(0,0)$ ）、位 $1$ （ $(0,1)$ ）、位 $3$ （ $(1,1)$ ）→ 1011 (11)
$6 \oplus 11 = 13$ （二进制 1101，即 $[[1,0],[0,1]]$ ）

继续 BFS 直到状态变为 $0$ 。

思路 1：代码

from collections import deque

class Solution:
    def minFlips(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        # 状态压缩：将矩阵转为整数
        start = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j]:
                    start |= 1 << (i * n + j)

        # 如果已经是全零
        if start == 0:
            return 0

        # 四个方向（上、下、左、右）
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        total = m * n

        # 预处理每个位置的反转掩码
        masks = []
        for i in range(m):
            for j in range(n):
                mask = 1 << (i * n + j)  # 自己
                for di, dj in dirs:
                    ni, nj = i + di, j + dj
                    if 0 <= ni < m and 0 <= nj < n:
                        mask |= 1 << (ni * n + nj)
                masks.append(mask)

        # BFS
        q = deque([(start, 0)])
        visited = set([start])

        while q:
            state, steps = q.popleft()
            for mask in masks:
                next_state = state ^ mask
                if next_state == 0:
                    return steps + 1
                if next_state not in visited:
                    visited.add(next_state)
                    q.append((next_state, steps + 1))

        return -1

思路 1：复杂度分析

时间复杂度： $O(2^{mn} \times mn)$ ，总状态数 $2^{mn}$ 最多 $2^9 = 512$ ，每个状态扩展 $mn$ 次（最多 $9$ 次），实际运行非常快。
空间复杂度： $O(2^{mn})$ ，需要存储所有已访问状态。

思路 2：DFS 枚举所有操作组合

由于状态空间极小，还可以直接枚举所有可能的操作组合（每个格子可以选或不选，共 $2^{mn}$ 种可能），检查是否能使矩阵变为全 $0$ ，取操作次数最少的一种。这和思路 1 本质相同，BFS 的优势在于它找到的就是最短路径，不需要全部枚举完再取最小值。