// Time:  O((m * n) * 2^(m * n))
// Space: O((m * n) * 2^(m * n))

class Solution {
public:
    int minFlips(vector<vector<int>>& mat) {
        static const vector<pair<int, int>> directions{{0, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int start = 0;
        for (int r = 0; r < mat.size(); ++r) {
            for (int c = 0; c < mat[0].size(); ++c) {
                start |= mat[r][c] << r * mat[0].size() + c;
            }
        }
        queue<pair<int, int>> q({{start, 0}});
        unordered_set<int> lookup = {start};
        while (!q.empty()) {
            const auto [state, step] = q.front(); q.pop();
            if (!state) {
                return step;
            }
            for (int r = 0; r < mat.size(); ++r) {
                for (int c = 0; c < mat[0].size(); ++c) {
                    int new_state = state;
                    for (const auto& [dr, dc] : directions) {
                        const auto& [nr, nc] = make_pair(r + dr, c + dc);
                        if (0 <= nr && nr < mat.size() &&
                            0 <= nc && nc < mat[0].size()) {
                            new_state ^= 1 << nr * mat[0].size() + nc;
                        }
                    }
                    if (lookup.count(new_state)) {
                        continue;
                    }
                    lookup.emplace(new_state);
                    q.emplace(new_state, step + 1);
                 }
            }
        }
        return -1;
    }
};