leetcode/200.cc at master · Coordinate36/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// class Solution {
// public:
//     int numIslands(vector<vector<char>>& grid) {
//         if (grid.empty()) {
//             return 0;
//         }
//         vector<vector<char>> cloned(grid.cbegin(), grid.cend());
//         int ans = 0;
//         for (int row = 0; row < grid.size(); ++row) {
//             for (int col = 0; col < grid[0].size(); ++col) {
//                 if (cloned[row][col] == '1') {
//                     ++ans;
//                     bfs(cloned, row, col);
//                 }
//             }
//         }
//         return ans;
//     }

//     void bfs(vector<vector<char>>& grid, int row, int col) {
//         vector<pair<int, int>> st;
//         st.push_back({row, col});
//         while (st.size()) {
//             auto p = st.back();
//             grid[p.first][p.second] = 0;
//             st.pop_back();
//             if (p.first && grid[p.first-1][p.second] == '1') {
//                 st.push_back({p.first - 1, p.second});
//             }
//             if (p.first + 1 < grid.size() && grid[p.first+1][p.second] == '1') {
//                 st.push_back({p.first + 1, p.second});
//             }
//             if (p.second && grid[p.first][p.second-1] == '1') {
//                 st.push_back({p.first, p.second - 1});
//             }
//             if (p.second + 1 < grid[0].size() && grid[p.first][p.second+1] == '1') {
//                 st.push_back({p.first, p.second + 1});
//             }
//         }
//     }
// };


class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) {
            return 0;
        }
        vector<vector<char>> cloned(grid.cbegin(), grid.cend());
        int ans = 0;
        for (int row = 0; row < grid.size(); ++row) {
            for (int col = 0; col < grid[0].size(); ++col) {
                if (cloned[row][col] == '1') {
                    ++ans;
                    dfs(cloned, row, col);
                }
            }
        }
        return ans;
    }

    void dfs(vector<vector<char>>& grid, int row, int col) {
        grid[row][col] = 0;
        if (row > 0 && grid[row-1][col] == '1') {
            dfs(grid, row - 1, col);
        }
        if (row + 1 < grid.size() && grid[row+1][col] == '1') {
            dfs(grid, row + 1, col);
        }
        if (col > 0 && grid[row][col-1] == '1') {
            dfs(grid, row, col - 1);
        }
        if (col + 1 < grid[0].size() && grid[row][col+1] == '1') {
            dfs(grid, row, col + 1);
        }
    }
};