class Solution {
public:
    int minFlips(vector<vector<int>>& mat) {
        if(ok(mat))return 0;
        set<vector<vector<int>>> seen;
        queue<pair<int,vector<vector<int>>>> q;
        q.push(make_pair(0,mat));
        while(!q.empty()){
            //cout<<1<<endl;
            int step=q.front().first;
            auto m=q.front().second;
            q.pop();
            for(int i=0;i<m.size();i++){
                for(int j=0;j<m[0].size();j++){
                    flip(m,i,j);
                    if(ok(m))return step+1;
                    if(seen.find(m)==seen.end()){
                        seen.insert(m);
                        q.push(make_pair(step+1,m));
                    }
                    flip(m,i,j);
                }
            }
        }
        return -1;
    }

    int dx[5]={0,1,-1,0,0};
    int dy[5]={0,0,0,1,-1};

    void flip(vector<vector<int>>& m,int x,int y){
        for(int i=0;i<5;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx>=0&&nx<m.size()&&ny>=0&&ny<m[0].size())m[nx][ny]=1-m[nx][ny];
        }
    }

    bool ok(vector<vector<int>>& mat){
        for(auto &v:mat)for(auto &i:v)if(i==1)return false;
        return true;
    }
};