题解 | #岛屿数量#

岛屿数量

https://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e

#include <functional>
class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& grid) {
        int m = grid.size();
        if (m == 0) {
            return 0;
        }
        int n = grid[0].size();
        if (n == 0) {
            return 0;
        }
        function<void(int, int)> dfs = [&](int i, int j) -> void {
            grid[i][j] = '0';
            if (i > 0 && grid[i - 1][j] == '1') {
                dfs(i - 1, j);
            }
            if (i < m - 1 && grid[i + 1][j] == '1') {
                dfs(i + 1, j);
            }
            if (j > 0 && grid[i][j - 1] == '1') {
                dfs(i, j - 1);
            }
            if (j < n - 1 && grid[i][j + 1] == '1') {
                dfs(i, j + 1);
            }
        };
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    ++res;
                    dfs(i, j);
                }
            }
        }
        return res;
    }
};

思路:dfs

每遇到一块陆地,就增加一个岛屿计数,然后遍历该岛屿,把岛屿变成海洋,就能确保下次不选中相同岛屿上的陆地。

全部评论

相关推荐

昨天 13:48
门头沟学院 C++
点赞 评论 收藏
分享
点赞 评论 收藏
分享
练习生懒羊羊:开飞机把这个公司创飞吧
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务