力扣200. 岛屿数量

2023-12-28 12:14:27

深度优先搜索

  • 思路:
    • 假设在 (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);
        }
    }
};

文章来源:https://blog.csdn.net/N_BenBird/article/details/135258861
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。