SHARE
TWEET

Untitled

a guest Dec 7th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int minFlips(vector<vector<int>>& mat) {
  4.         if(ok(mat))return 0;
  5.         set<vector<vector<int>>> seen;
  6.         queue<pair<int,vector<vector<int>>>> q;
  7.         q.push(make_pair(0,mat));
  8.         while(!q.empty()){
  9.             //cout<<1<<endl;
  10.             int step=q.front().first;
  11.             auto m=q.front().second;
  12.             q.pop();
  13.             for(int i=0;i<m.size();i++){
  14.                 for(int j=0;j<m[0].size();j++){
  15.                     flip(m,i,j);
  16.                     if(ok(m))return step+1;
  17.                     if(seen.find(m)==seen.end()){
  18.                         seen.insert(m);
  19.                         q.push(make_pair(step+1,m));
  20.                     }
  21.                     flip(m,i,j);
  22.                 }
  23.             }
  24.         }
  25.         return -1;
  26.     }
  27.    
  28.     int dx[5]={0,1,-1,0,0};
  29.     int dy[5]={0,0,0,1,-1};
  30.    
  31.     void flip(vector<vector<int>>& m,int x,int y){
  32.         for(int i=0;i<5;i++){
  33.             int nx=x+dx[i],ny=y+dy[i];
  34.             if(nx>=0&&nx<m.size()&&ny>=0&&ny<m[0].size())m[nx][ny]=1-m[nx][ny];
  35.         }
  36.     }
  37.    
  38.     bool ok(vector<vector<int>>& mat){
  39.         for(auto &v:mat)for(auto &i:v)if(i==1)return false;
  40.         return true;
  41.     }
  42. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top