力扣200. 岛屿数量-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣200. 岛屿数量。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

深度优先搜索

思路：
- 假设在 (r, c) 格子位置，r 为所处行，c 为所处的列；
- 遇到陆地格子之后，遍历搜索其上下左右周围的陆地格子，但是不能超出边界，即对应的数组下标不越界；
- 为了避免重复多次搜索，搜索到陆地格子之后将其标记染色；
- 四周搜索完所有的陆地格子，即为一个岛屿；

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (nr == 0) {
            return 0;
        }
        int nc = grid[0].size();

        int num = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num;
                    dfs(grid, r, c);
                }
            }
        }

        return num;
    }

private:
    void dfs(std::vector<std::vector<char>>& grid, int r, int c) {
        int nr = grid.size();
        int nc = grid[0].size();

        // mark
        grid[r][c] = '0';

        // up
        if (r - 1 >= 0 && grid[r - 1][c] == '1') {
            dfs(grid, r - 1, c);
        }
        // down
        if (r + 1 < nr && grid[r + 1][c] == '1') {
            dfs(grid, r + 1, c);
        }
        // left
        if (c - 1 >= 0 && grid[r][c - 1] == '1') {
            dfs(grid, r, c - 1);
        }
        // right
        if (c + 1 < nc && grid[r][c + 1] == '1') {
            dfs(grid, r, c + 1);
        }
    }
};