200. Number of Islands

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 class Solution {
 6     
 7 private:
 8     int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
 9     int m, n;
10     vector<vector<bool> > visited;
11     
12     bool inArea(int x, int y) {
13         return x >= 0 && x < m && y >= 0 && y < n;
14     }
15     
16     void dfs(vector<vector<char> >& grid, int x, int y) {
17         
18         visited[x][y] = true;
19         for(int i = 0; i < 4; ++ i) {
20             
21             int newX = x + dir[i][0];
22             int newY = y + dir[i][1];
23             if(inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == '1') {
24                 dfs(grid, newX, newY);
25             }
26         }
27         
28         return ;
29     }
30       
31 public:
32     int numIslands(vector<vector<char> >& grid) {
33         
34         m = grid.size();
35         if(m == 0)    return 0;
36         
37         n = grid[0].size();
38         if(n == 0)    return 0;
39             
40         for(int i = 0; i < m; ++ i)
41             visited.push_back(vector<bool>(n, false));
42             
43         int res = 0;
44         for(int i = 0; i < m; ++ i) {
45             for(int j = 0; j < n; ++ j) {
46                 if(grid[i][j] == '1' && !visited[i][j]) {
47                     dfs(grid, i, j);
48                     res ++;
49                 }
50             }
51         }
52         return res;
53     }
54 };
55 
56 int main()
57 {
58     char g1[4][5] = {
59         {'1','1','1','1','0'},
60         {'1','1','0','1','0'},
61         {'1','1','0','0','0'},
62         {'0','0','0','0','0'}
63     };
64     vector<vector<char> > grid1;
65     for(int i = 0; i < 4; ++ i)
66         grid1.push_back(vector<char>(g1[i], g1[i] + sizeof(g1[i])/sizeof(char)));
67     
68     cout << Solution().numIslands(grid1) << endl;    
69     
70     return 0;
71 }

 1 #include <iostream>
 2 #include <vector>
 3 #include <stack>
 4 using namespace std;
 5 
 6 class Solution {
 7     
 8     private:
 9         int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
10         int m, n;
11         
12     public:
13         
14         int numIslands(vector<vector<char>>& grid) {
15             
16             m = grid.size();
17             if(m == 0)    return 0;
18             n = grid[0].size();
19             if(n == 0)  return 0;
20             
21             vector<vector<bool> > visited(m, vector<bool>(n, false));
22             
23             int res = 0;
24             for(int i = 0; i < m; ++ i) {
25                 for(int j = 0; j < n; ++ j) {
26                     if(grid[i][j] == '1' && !visited[i][j]) {
27                         dfs(grid, i, j, visited);
28                         res ++;
29                     }
30                 }
31             }
32             return res;
33         }
34         
35     private:
36         void dfs(vector<vector<char> >& grid, int x, int y, vector<vector<bool> >& visited) {
37             
38             stack<pair<int, int> > q;
39             q.push(make_pair(x, y));
40             visited[x][y] = true;
41             while(!q.empty()) {
42                 int curx = q.top().first;
43                 int cury = q.top().second;
44                 q.pop();
45                 
46                 for(int i = 0; i < 4; ++ i) {
47                     int newX = curx + dir[i][0];
48                     int newY = cury + dir[i][1];
49                     if(inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == '1') {
50                         q.push(make_pair(newX, newY));
51                         visited[newX][newY] = true;
52                     }
53                 }
54             }
55             
56             return ;
57         }
58         
59         bool inArea(int x, int y) {
60             return x >= 0 && x < m && y >= 0 && y < n;
61         }
62 };
63 
64 int main()
65 {
66     vector<vector<char>> grid1 = {
67         {'1','1','1','1','0'},
68         {'1','1','0','1','0'},
69         {'1','1','0','0','0'},
70         {'0','0','0','0','0'}
71     };
72     
73     cout << Solution().numIslands(grid1) << endl;
74     
75     return 0;
76 }

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 
 6 class Solution {
 7     
 8     private:
 9         int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
10         int m, n;
11     
12     public:
13         
14         int numIslands(vector<vector<char>>& grid) {
15             
16             m = grid.size();
17             if(m == 0)    return 0;
18             n = grid[0].size();
19             if(n == 0)  return 0;
20             
21             vector<vector<bool> > visited(m, vector<bool>(n, false));
22             
23             int res = 0;
24             for(int i = 0; i < m; ++ i) {
25                 for(int j = 0; j < n; ++ j) {
26                     if(grid[i][j] == '1' && !visited[i][j]) {
27                         bfs(grid, i, j, visited);
28                         res ++;
29                     }
30                 }
31             }
32             
33             return res;
34         }
35         
36     private:
37         
38         void bfs(vector<vector<char> >& grid, int x, int y, vector<vector<bool> >& visited) {
39             
40             queue<pair<int, int> > q;
41             q.push(make_pair(x, y));
42             visited[x][y] = true;
43             while(!q.empty()) {
44                 
45                 int curx = q.front().first;
46                 int cury = q.front().second;
47                 q.pop();
48                 
49                 for(int i = 0; i < 4; ++ i) {
50                     int newX = curx + dir[i][0];
51                     int newY = cury + dir[i][1];
52                     if(inArea(newX, newY) && !visited[newX][newY] && grid[newX][newY] == '1') {
53                         q.push(make_pair(newX, newY));
54                         visited[newX][newY] = true;
55                     }
56                 }
57             }
58             
59             return ;
60         }
61         
62         bool inArea(int x, int y) {
63             return x >= 0 && x < m && y >= 0 && y < n;
64         }
65 };
66 
67 int main()
68 {
69     vector<vector<char> > grid1 = {
70         {'1','1','1','1','0'},
71         {'1','1','0','1','0'},
72         {'1','1','0','0','0'},
73         {'0','0','0','0','0'}
74     };
75     
76     cout << Solution().numIslands(grid1) << endl;
77     
78     return 0;
79 }

  1 #include <iostream>
  2 #include <vector>
  3 #include <unordered_set>
  4 using namespace std;
  5 
  6 class UnionFind {
  7     
  8     private:
  9         vector<int> rank, parent;
 10         
 11     public:
 12         
 13         UnionFind(int n) {
 14             rank.clear();
 15             parent.clear();
 16             for(int i = 0; i < n; ++ i) {
 17                 parent.push_back(i);
 18                 rank.push_back(i);
 19             }
 20         }
 21         
 22         int find(int p) {
 23             
 24             while(p != parent[p]) {
 25                 parent[p] = parent[parent[p]];
 26                 p = parent[p];
 27             }
 28             return p;
 29         }
 30         
 31         bool isConnected(int p, int q) {
 32             return find(p) == find(q);
 33         }
 34         
 35         void unionElements(int p, int q) {
 36             
 37             int pRoot = find(p);
 38             int qRoot = find(q);
 39             
 40             if(pRoot == qRoot)    return ;
 41             
 42             if(rank[pRoot] < rank[qRoot]) {
 43                 parent[pRoot] = qRoot;
 44             }
 45             else if(rank[qRoot] < rank[pRoot]) {
 46                 parent[qRoot] = pRoot;
 47             }
 48             else {
 49                 parent[pRoot] = qRoot;
 50                 rank[qRoot] += 1;
 51             }
 52         }
 53 };
 54 
 55 class Solution {
 56     
 57     private:
 58         int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
 59         int m, n; 
 60     
 61     public:
 62         
 63         int numIslands(vector<vector<char>>& grid) {
 64             
 65             m = grid.size();
 66             if(m == 0)  return 0;
 67             n = grid[0].size();
 68             if(n == 0)    return 0;
 69             
 70             UnionFind uf(m * n);
 71             for(int i = 0; i < m; ++ i) {
 72                 for(int j = 0; j < n; ++ j) {
 73                     if(grid[i][j] == '1') {
 74                         for(int k = 0; k < 4; ++ k) {
 75                             int newX = i + dir[k][0];
 76                             int newY = j + dir[k][1];
 77                             if(inArea(newX, newY) && grid[newX][newY] == '1') {
 78                                 uf.unionElements(i * n + j, newX * n + newY);
 79                             }
 80                         }
 81                     }
 82                 }
 83             }
 84             unordered_set<int> regions;
 85             for(int i = 0; i < m; ++ i) {
 86                 for(int j = 0; j < n; ++ j) {
 87                     if(grid[i][j] == '1') {
 88                         regions.insert(uf.find(i * n + j));
 89                     }
 90                 }
 91             }
 92             return regions.size();
 93         }
 94         
 95     private:
 96         bool inArea(int x, int y) {
 97             return x >= 0 && x < m && y >= 0 && y < n;
 98         }
 99 };
100 
101 int main()
102 {
103     vector<vector<char> > grid1 = {
104             {'1','1','1','1','0'},
105             {'1','1','0','1','0'},
106             {'1','1','0','0','0'},
107             {'0','0','0','0','0'}    
108     };
109     cout << Solution().numIslands(grid1) << endl;
110     
111     return 0;
112 }