Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement