# 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