LeetCode - Number of Islands

11110
11010
11000
00000

11000
11000
00100
00011

 1 // 3CE, 1WA, 1AC, solution using DFS
 2 class Solution {
 3 public:
 4     Solution() {
 5         d[0][0] = -1;
 6         d[0][1] = 0;
 7         d[1][0] = +1;
 8         d[1][1] = 0;
 9         d[2][0] = 0;
10         d[2][1] = -1;
11         d[3][0] = 0;
12         d[3][1] = +1;
13     }
14 
15     int numIslands(vector<vector<char>> &grid) {
16         n = grid.size();
17         if (n == 0) {
18             return 0;
19         }
20         m = grid[0].size();
21         if (m == 0) {
22             return 0;
23         }
24         
25         int cc = 0;
26         int i, j;
27         
28         b.resize(n, vector<bool>(m, false));
29         for (i = 0; i < n; ++i) {
30             for (j = 0; j < m; ++j) {
31                 if (grid[i][j] == ‘1‘ && !b[i][j]) {
32                     DFS(i, j, grid);
33                     ++cc;
34                 }
35             }
36         }
37         b.clear();
38         
39         return cc;
40     }
41 protected:
42     int n, m;
43     vector<vector<bool> > b;
44     int d[4][2];
45     
46     void DFS(int x, int y, vector<vector<char> > &grid) {
47         b[x][y] = true;
48         int i;
49         int x1, y1;
50         
51         for (i = 0; i < 4; ++i) {
52             x1 = x + d[i][0];
53             y1 = y + d[i][1];
54             if (x1 < 0 || x1 > n - 1 || y1 < 0 || y1 > m - 1) {
55                 continue;
56             }
57             if (grid[x1][y1] == ‘0‘ || b[x1][y1]) {
58                 continue;
59             }
60             DFS(x1, y1, grid);
61         }
62     }
63 };

 1 // 1AC, solution using BFS
 2 #include <queue>
 3 using namespace std;
 4 
 5 class Solution {
 6 public:
 7     Solution() {
 8         d[0][0] = -1;
 9         d[0][1] = 0;
10         d[1][0] = +1;
11         d[1][1] = 0;
12         d[2][0] = 0;
13         d[2][1] = -1;
14         d[3][0] = 0;
15         d[3][1] = +1;
16     }
17 
18     int numIslands(vector<vector<char>> &grid) {
19         n = grid.size();
20         if (n == 0) {
21             return 0;
22         }
23         m = grid[0].size();
24         if (m == 0) {
25             return 0;
26         }
27         
28         int cc = 0;
29         int i, j;
30         
31         b.resize(n, vector<bool>(m, false));
32         for (i = 0; i < n; ++i) {
33             for (j = 0; j < m; ++j) {
34                 if (grid[i][j] == ‘1‘ && !b[i][j]) {
35                     BFS(i, j, grid);
36                     ++cc;
37                 }
38             }
39         }
40         b.clear();
41         
42         return cc;
43     }
44 protected:
45     int n, m;
46     vector<vector<bool> > b;
47     int d[4][2];
48     
49     void BFS(int x, int y, vector<vector<char> > &grid) {
50         queue<int> q;
51         int i;
52         int x1, y1;
53         int p;
54         
55         q.push(x * m + y);
56         b[x][y] = true;
57         while (!q.empty()) {
58             p = q.front();
59             q.pop();
60             x = p / m;
61             y = p % m;
62             for (i = 0; i < 4; ++i) {
63                 x1 = x + d[i][0];
64                 y1 = y + d[i][1];
65                 if (x1 < 0 || x1 > n - 1 || y1 < 0 || y1 > m - 1) {
66                     continue;
67                 }
68                 if (grid[x1][y1] == ‘0‘ || b[x1][y1]) {
69                     continue;
70                 }
71                 q.push(x1 * m + y1);
72                 b[x1][y1] = true;
73             }
74         }
75     }
76 };