岛屿数量

岛屿数量

题目描述

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

示例1

1
2
3
4
5
6
7
输入:
11110
11010
11000
00000

输出: 1

示例2

1
2
3
4
5
6
7
输入:
11000
11000
00100
00011

输出: 3

分析

  1. 思路: 找到一个陆地,通过利用队列,将其相连的陆地都变成海洋。

  2. 实现: 设置双层循环,找到一个陆地,加入队列,通过队列不断将与其相连的陆地变成海洋。在队列循环外,每遍历完一块陆地,计数器值就加一

    参考代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    class Solution {
    public:
    int numIslands(vector<vector<char>>& grid) {
    int row = grid.size();
    if(row == 0){return 0 ;}
    int col = grid[0].size();
    int cnt = 0;
    for(int i = 0 ; i < row ; ++i)
    {
    for(int j = 0 ; j < col ; ++j)
    {
    if(grid[i][j] == '1')
    {
    ++cnt;
    grid[i][j] = '0';
    queue<pair<int,int>> q ;
    q.push({i,j});
    while(!q.empty())
    {
    auto s = q.front();
    q.pop();
    int rows = s.first ;
    int cols = s.second;
    if(rows + 1 < row && grid[rows + 1][cols] == '1')
    {
    q.push({rows+1,cols});
    grid[rows+1][cols] = '0';
    }
    if( cols +1 < col && grid[rows][cols+1] == '1')
    {
    q.push({rows,cols+1});
    grid[rows][cols+1] = '0';
    }
    if(rows - 1 >= 0 && grid[rows-1][cols] == '1')
    {
    q.push({rows-1,cols});
    grid[rows-1][cols] = '0';
    }
    if(cols-1>= 0 && grid[rows][cols-1] == '1')
    {
    q.push({rows,cols-1});
    grid[rows][cols-1] = '0';
    }
    }
    }
    }
    }
    return cnt;
    }
    };
作者

瑾年

发布于

2021-07-17

更新于

2021-07-17

许可协议

CC BY-NC-SA 4.0

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×