Guest User

Untitled

a guest
Dec 7th, 2019
100
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