1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

https://leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/

由01组成矩阵每次能选择一个位置把它和周围的（如存在）四个点取反，问变成零阵至少需要多少步。min step => BFS/DP，暴力遍历所有可能的flip方式，用bitmap存每个状态。

还有利用线性代数里结论的三次方时间复杂度解法。

class Solution {
public:
    int minFlips(vector<vector<int>>& mat) {
        const int M = mat.size(), N = mat[0].size();
        int bitmap = 0;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                bitmap |= mat[i][j] << (i * N + j);
            }
        }
        vector<vector<int>> dirs{{0, -1}, {0, 1}, {-1, 0}, {1, 0}, {0, 0}};
        const auto flip = [&](int bitmap, int i, int j) {
            for (const auto &d : dirs) {
                int r = i + d[0], c = j + d[1];
                if (r >= 0 && r < M && c >= 0 && c < N) {
                    bitmap ^= 1 << (r * N + c);
                }
            }
            return bitmap;
        };
        queue<int> q;
        unordered_set<int> visited(bitmap);
        q.push(bitmap);
        for (int cnt = 0; !q.empty(); ++cnt) {
            for (int size = q.size(); size > 0; --size) {
                bitmap = q.front(); q.pop();
                if (bitmap == 0) return cnt;
                for (int i = 0; i < M; ++i) {
                    for (int j = 0; j < N; ++j) {
                        const auto next = flip(bitmap, i, j);
                        if (visited.count(next)) continue;
                        visited.insert(next);
                        q.push(next);
                    }
                }
            }
        }
        return -1;
    }
};