Leetcode 200.岛屿数量——dfs

举报
陈沧夜 发表于 2022/05/01 22:50:53 2022/05/01
【摘要】 Leetcode 200.岛屿数量——dfs 题目 给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向...

Leetcode 200.岛屿数量——dfs

题目

给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

示例 1:

输入:

11110
11010
11000
00000

输出: 1
示例 2:

输入:

11000
11000
00100
00011

输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-islands

思路

首先从某个坐标开始进行深度遍历,遍历过的地方将其改为0。遍历完这一趟我们会发现这趟遍历遍历了一个岛。

接下来我们寻找其他的为1的坐标继续遍历即可

代码

class Solution {
private:
  void dfs(vector<vector<char>>& grid, int r, int c) {
    int nr = grid.size();	//求出列宽
    int nc = grid[0].size();	//求出行宽

    grid[r][c] = '0';
     //判断边界,并遍历
    if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
    if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
    if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
    if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
  }

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

    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {//逐列逐行遍历查找1的点,并进行深度遍历
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          dfs(grid, r, c);
        }
      }
    }

    return num_islands;
  }
};

文章来源: blog.csdn.net,作者:沧夜2021,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/CANGYE0504/article/details/105636298

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。