Eric 的小站

1
输入：grid = [
2
  ["1","1","1","1","0"],
3
  ["1","1","0","1","0"],
4
  ["1","1","0","0","0"],
5
  ["0","0","0","0","0"]
6
]
7
输出：1

1
输入：grid = [
2
  ["1","1","0","0","0"],
3
  ["1","1","0","0","0"],
4
  ["0","0","1","0","0"],
5
  ["0","0","0","1","1"]
6
]
7
输出：3

1
class Solution {
2
public:
3
    void dfs(vector<vector<char>>& grid, int i, int j) {
4
        int i_num = grid.size();
5
        int j_num = grid[0].size();
6

7
        grid[i][j] = '0';
8

9
        if (i - 1 >= 0 && grid[i - 1][j] == '1')
10
            dfs(grid, i - 1, j);
11
        if (i + 1 < i_num && grid[i + 1][j] == '1')
12
            dfs(grid, i + 1, j);
13
        if (j - 1 >= 0 && grid[i][j - 1] == '1')
14
            dfs(grid, i, j - 1);
15
        if (j + 1 < j_num && grid[i][j + 1] == '1')
16
            dfs(grid, i, j + 1);
17
    }
18
    int numIslands(vector<vector<char>>& grid) {
19
        int i_num = grid.size();
20
        if (!i_num)
21
            return 0;
22
        int j_num = grid[0].size();
23

24
        int ans = 0;
25
        for (int i = 0; i < i_num; i++) {
26
            for (int j = 0; j < j_num; j++) {
27
                if (grid[i][j] == '1') {
28
                    ++ans;
29
                    dfs(grid, i, j);
30
                }
31
            }
32
        }
33
        return ans;
34
    }
35
};