1284

class Solution {
public:
    int minFlips(vector<vector<int>>& mat) {
        int start=0, n=mat.size(), m=mat[0].size();
        int dx[5] = {0, 1, -1, 0, 0};
        int dy[5] = {0, 0, 0, 1, -1};

        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                start |= (mat[i][j] << (i*m+j));

        queue<pair<int, int>> q;
        bool vis[(1<<n*m)+1];
        memset(vis, false, sizeof(vis));

        // Push the start element in queue;
        q.push({start, 0});
        vis[start] = true;

        while(!q.empty()){
            pair<int, int> p = q.front();
            q.pop();

            // If zero matrix found.
            if(!p.first) return p.second;

            // Flip each bit to get next state of matrix;
            for(int i=0; i<n; i++)
                for(int j=0; j<m; j++){
                    int next = p.first;
                    for(int k=0; k<5; k++){
                        int x = i+dx[k], y = j+dy[k];
                        if(x>=0 && x<n && y>=0 && y<m)
                            next ^= (1<<(x*m+y));
                    }
                    // If next state is not visited, insert in queue.
                    if(!vis[next]){
                        vis[next] = true;
                        q.push({next, p.second+1});
                    }
                }
        }
        return -1;
    }
};