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

Given a m x n binary matrix mat. In one step, you can choose one cell and flip it and all the four neighbors of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighbors if they share one edge.

Return the minimum number of steps required to convert mat to a zero matrix or -1 if you cannot.

A binary matrix is a matrix with all cells equal to 0 or 1 only.

A zero matrix is a matrix with all cells equal to 0.

class Solution {
    vector<int> buildFlip(vector<vector<int>>& mat) {
        vector<int> res;
        int n = mat.size(), m = mat[0].size(), dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                int value = (1<<mat[i][j]);
                for(int k = 0; k < 4; k++) {
                    int nx = j + dx[k], ny = i + dy[k];
                    if(0 <= nx && nx < m && 0 <= ny && ny < n) value |= (1<<mat[ny][nx]);
                }
                res.push_back(value);
            }
        }
        return res;
    }
public:
    int minFlips(vector<vector<int>>& mat) {
        int len(0), init(0), res(0);
        for(int i = 0; i < mat.size(); i++) {
            for(int j = 0; j < mat[i].size(); j++) {
                if(mat[i][j]) init |= (1<<len);
                mat[i][j] = len++;
            }
        }
        vector<int> flip = buildFlip(mat);
        queue<int> q;
        q.push(init);
        set<int> v {init};
        while(!q.empty() and !v.count(0)) {
            int size = q.size();
            while(size--) {
                int num = q.front();
                q.pop();
                for(auto& f : flip) {
                    int next = num ^ f;
                    if(!v.count(next)) {
                        v.insert(next);
                        q.push(next);
                    }
                }
            }
            res++;
        }

        return v.count(0) ? res : -1;
    }
};