转化为全零矩阵的最少反转次数

在一个只有 0 和 1 的小网格（最大 $3 \times 3$）中，每次选择一个格子翻转时其上下左右相邻的格子也会随之一起翻转（0 变 1，1 变 0）；目标是求出将整个网格全部变为 0 所需要的最少翻转次数，若无法完成则返回 -1。

August 5, 2015LeetCode1分钟阅读

给你一个 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.length

n == mat[0].length

1 <= m <= 3

1 <= n <= 3

mat[i][j] 是 0 或 1 。

由于矩阵的行数 $m$ 和列数 $n$ 极小（ $1 \le m, n \le 3$ ，最多仅 9 个格子），状态总数最多只有 $2^9 = 512$ 种。求解“最少反转次数”即在状态图上寻找最短路径，因此最佳解法是 广度优先搜索（BFS）+ 位运算压缩。

二进制状态压缩：
- 将 $m \times n$ 的二维矩阵按行展开拉平为一个一维索引：(i * n + j)。
- 用一个 int 整数（即二进制 Bitmask）表示矩阵状态。第 k 位为 1 表示格子为 1，为 0 表示格子为 0。
- 全零矩阵即对应状态 0。
状态转移（反转操作）：
- 翻转位置 $(r, c)$ 及其上下左右相邻格子时，利用按位异或（XOR）操作实现 $0 \leftrightarrow 1$ 的切换。
- 翻转掩码为 1 << (r * n + c)。
异或运算（XOR，符号 ^ 或 $\oplus$ ）是一种二进制逻辑运算，核心法则是“同为 0，异为 1”——当两个输入相同时结果为 0，不同时结果为 1。
BFS 寻找最短路径：
- 从初始矩阵对应的状态 start 出发进行 BFS 遍历。
- 使用 visited 数组/哈希表记录已访问过的状态，防止死循环。
- 第一次搜索到状态 0 时的层数（步数）即为最少反转次数；若队列为空仍无法到达 0，则返回 -1。

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int minFlips(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();

        // 1. 将初始矩阵压缩为一个 int 整数
        int start = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 1) {
                    start |= (1 << (i * n + j));
                }
            }
        }

        // 若原本就是全零矩阵，直接返回 0
        if (start == 0) return 0;

        // 2. BFS 初始化
        queue<pair<int, int>> q; // {当前状态 mask, 步数 steps}
        vector<bool> visited(1 << (m * n), false);

        q.push({start, 0});
        visited[start] = true;

        // 方向数组：上下左右 + 当前位置（共 5 个位置受影响）
        int dirs[5][2] = {{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        // 3. BFS 搜索
        while (!q.empty()) {
            auto [curr, steps] = q.front();
            q.pop();

            // 尝试翻转每一个格子 (i, j)
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    int next_state = curr;

                    // 计算翻转 (i, j) 及其四周影响后的新状态
                    for (auto& d : dirs) {
                        int ni = i + d[0];
                        int nj = j + d[1];
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
                            next_state ^= (1 << (ni * n + nj)); // 按位异或取反
                        }
                    }

                    // 达到全零矩阵
                    if (next_state == 0) {
                        return steps + 1;
                    }

                    // 如果是新状态，加入队列
                    if (!visited[next_state]) {
                        visited[next_state] = true;
                        q.push({next_state, steps + 1});
                    }
                }
            }
        }

        return -1; // 无法转化为全零矩阵
    }
};

时间复杂度： $O(m \cdot n \cdot 2^{m \cdot n})$ 。状态数量上限为 $2^{m \cdot n} \le 512$ ，每个状态最多扩展 $m \times n \le 9$ 次，整体计算量约几千次操作，能在 1 毫秒内秒杀。
空间复杂度： $O(2^{m \cdot n})$ 。队列和 visited 数组的大小最大为 512，极度节省空间。

核心思路

参考代码

复杂度分析