岛屿数量


题目描述

给定一个由 ‘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;
        }
    };

文章作者: 瑾年
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 瑾年 !
  目录