1 #define _for(i,a,b) for(int i = (a);i < (b);i ++) 2 #define pb push_back 3 class Solution 4 { 5 public: 6 vector<int> root; 7 int _find(int x) 8 { 9 if(root[x]==x) return x; 10 return root[x] = _find(root[x]); 11 } 12 void merge(int x,int y) 13 { 14 int rx = _find(x); 15 int ry = _find(y); 16 if(rx==ry) return ; 17 _for(i,0,root.size()) 18 if(root[i]==rx) 19 root[i] = ry; 20 } 21 int regionsBySlashes(vector<string>& grid) 22 { 23 int sz = grid.size(); 24 vector<vector<pair<int,int>>> v(sz,vector<pair<int,int>>(sz)); 25 26 int k = 1; 27 _for(i,0,grid.size()) 28 _for(j,0,grid.size()) 29 if(grid[i][j]==' ') 30 v[i][j].first = v[i][j].second = k++; 31 else 32 { 33 v[i][j].first = k++; 34 v[i][j].second = k++; 35 } 36 37 _for(i,0,k) 38 root.pb(i); 39 _for(i,0,grid.size()) 40 { 41 _for(j,0,grid.size()) 42 { 43 if(i!=0) 44 if(grid[i][j]=='/') 45 { 46 if(grid[i-1][j]=='/') 47 merge(v[i-1][j].second,v[i][j].first); 48 else 49 merge(v[i-1][j].first,v[i][j].first); 50 } 51 else if(grid[i][j]=='\') 52 { 53 if(grid[i-1][j]=='\') 54 merge(v[i-1][j].first,v[i][j].second); 55 else 56 merge(v[i-1][j].second,v[i][j].second); 57 } 58 else 59 { 60 if(grid[i-1][j]=='\') 61 merge(v[i-1][j].first,v[i][j].second); 62 else 63 merge(v[i-1][j].second,v[i][j].second); 64 } 65 if(j!=0) 66 merge(v[i][j-1].second,v[i][j].first); 67 } 68 } 69 70 set<int> s; 71 int rnt = 0; 72 _for(i,0,root.size()) 73 if(!s.count(root[i])) 74 { 75 s.insert(root[i]); 76 rnt ++; 77 } 78 79 return rnt-1; 80 } 81 };
并查集就完事了铁纸们