题目描述

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

示例1

输入:
11110
11010
11000
00000

输出: 1

示例2

输入:
11000
11000
00100
00011

输出: 3

分析

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

    参考代码

    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;
    }
    };

谢谢访问