专栏首页Reck ZhangLeetCode 0200 - Number of Islands

LeetCode 0200 - Number of Islands

Number of Islands

Desicription

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

Solution

class Solution {
private:
    int n;
    int m;
    int dir[4][2] = {1, 0, -1, 0, 0, -1, 0, 1};
    void dfs(int x, int y, vector<vector<char>>& grid) {
        if(grid[x][y] == '1')
            grid[x][y] = '0';
        for(int i = 0; i < 4; i++) {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if(dx < 0 || dx == n || dy < 0 || dy >= m || grid[dx][dy] == '0')
                continue;
            dfs(dx, dy, grid);
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size() == 0)
            return 0;
        n = grid.size();
        m = grid[0].size();
        int res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == '1') {
                    res++;
                    dfs(i, j, grid);
                }
            }
        }
        return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode <BT> 200. Number of Islands

    Given a 2d grid map of '1's (land) and '0's (water), count the number of islands...

    大学里的混子
  • Leetcode 200. Number of Islands

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • LeetCode 200. Number of Islands (Tag:BFS)

    Given a 2d grid map of '1's (land) and '0's (water), count the number of islands...

    用户7447819
  • Leetcode 200 Number of Islands 并查集

    Given a 2d grid map of '1's (land) and '0's (water), count the number of islan...

    triplebee
  • LeetCode 200. Number of Islands(并查集)

    ShenduCC
  • Leetcode 200 Number of Islands 岛的个数

    1. 遍历每一个结点,如果某结点是陆地且未访问过,岛数目加1,修改未访问标志位,然后把该点放入队列中,以备扩展岛屿使用,进入2 2. 队列不为空时,取出点,然...

    程序员小王
  • LeetCode 200:岛屿数量 Number of Islands

    给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格...

    爱写bug
  • DFS&BFS - 200. Number of Islands

    Given a 2d grid map of '1's (land) and '0's (water), count the number of islands...

    用户5705150
  • LWC 53:694. Number of Distinct Islands

    LWC 53:694. Number of Distinct Islands 传送门:694. Number of Distinct Islands Probl...

    用户1147447
  • [LintCode] Number of Islands(岛屿个数)

    0代表海,1代表岛,如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

    HoneyMoose
  • 每日两题 T29

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

    合一大师
  • ​LeetCode刷题实战305:岛屿数量II

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • ​LeetCode刷题实战200:岛屿数量

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • LeetCode 305. 岛屿数量 II(并查集)

    起始的时候,每个格子的地形都被默认标记为「水」。 我们可以通过使用 addLand 进行操作,将位置 (row, col) 的「水」变成「陆地」。

    Michael阿明
  • Python3刷题系列(五)

    英文版:https://leetcode.com/problems/number-of-islands/description/

    用户5473628
  • AkShare-疫情数据-CSSE数据

    本次在 COVID-19 原有接口的基础上增加:美国约翰·霍普金斯大学系统科学与工程中心(JHU CSSE)收集各国卫生机构公开 2019-2020 年新型冠状...

    数据科学实战
  • Leetcode 463. Island Perimeter 解题

    好久没有刷题,甚是怀念这种刷题的感觉 最近有刷杭电oJ POJ也试着刷了一下,还有个国外的平台我忘了叫啥了 感觉LeetCode的平台很人性化,能够在提...

    vincentbbli
  • Board相关题

    Given a 2d grid map of '1's (land) and '0's (water), count the number of islands...

    王脸小
  • Leetcode 726. Number of Atoms

    文章作者:Tyan 博客:noahsnail.com | CSDN | 简书

    Tyan

扫码关注云+社区

领取腾讯云代金券