当前位置:网站首页>Leetcode 200.岛屿数量 BFS
Leetcode 200.岛屿数量 BFS
2022-08-10 19:06:00 【Alkali!】
题目描述
岛屿数量
给你一个由 '1'
(陆地)和 '0'
(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
思路
直接BFS求就完事了
代码
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
vector<vector<bool>> st(grid.size()); //标记数组
for(int i=0;i<grid.size();i++)
st[i].resize(grid[0].size());
for(int i=0;i<grid.size();i++) //初始化为未访问
for(int j=0;j<grid[0].size();j++)
st[i][j]=false;
int res=0; //岛屿数量
for(int i=0;i<grid.size();i++)
for(int j=0;j<grid[0].size();j++)
{
if(grid[i][j]=='1')
{
if(st[i][j]) continue;
else
{
res++;
bfs(st,i,j,grid); //bfs
}
}
}
return res;
}
void bfs(vector<vector<bool>>& st,int x,int y,vector<vector<char>>& gap)
{
int n=gap.size(),m=gap[0].size();
queue<pair<int,int>> q;
q.push({
x,y});
st[x][y]=true;
int dx[4]={
-1,0,1,0},dy[4]={
0,1,0,-1};
while(!q.empty())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int nx=t.first+dx[i],ny=t.second+dy[i];
if(nx<0||nx>=n||ny<0||ny>=m) continue; //出界
if(gap[nx][ny]=='0') continue; //没出界,但是0
if(st[nx][ny]) continue; //是1,但访问过了
q.push({
nx,ny});
st[nx][ny]=true;
}
}
}
};
边栏推荐
猜你喜欢
30分钟使用百度EasyDL实现健康码/行程码智能识别
[教你做小游戏] 斗地主的手牌,如何布局?看25万粉游戏区UP主怎么说
DefaultSelectStrategy NIOEventLoop执行策略
主动信息收集
RS-485多主机通信的组网方式评估
servlet映射路径匹配解析
ARouter使用自定义注解处理器,自动生成跳转Activity的代码,避免手动填写和管理path
转铁蛋白(Tf)修饰去氢骆驼蓬碱磁纳米脂质体/香豆素-6脂质体/多柔比星脂质体
[Teach you how to do mini-games] How to lay out the hands of Dou Dizhu?See what the UP master of the 250,000 fan game area has to say
测试/开发程序员值这么多钱么?“我“不会愿赌服输......
随机推荐
多线程与高并发(五)—— 源码解析 ReentrantLock
史上最全GIS相关软件(CAD、FME、Arcgis、ArcgisPro)
不止跑路,拯救误操作rm -rf /*的小伙儿
TDD、FDD是什么意思?
机器学习|模型评估——AUC
idea汉化教程[通俗易懂]
【无标题】基于Huffman和LZ77的GZIP压缩
【SemiDrive源码分析】【MailBox核间通信】52 - DCF Notify 实现原理分析 及 代码实战
杭电多校七 1003-Counting Stickmen(组合数学)
Keras深度学习实战(17)——使用U-Net架构进行图像分割
[Go WebSocket] 你的第一个Go WebSocket服务: echo server
【毕业设计】基于STM32的天气预报盒子 - 嵌入式 单片机 物联网
今日份bug,点击win10任务栏视窗动态壁纸消失的bug,暂未发现解决方法。
小分子PEG CAS:1352814-07-3生物素-PEG6-丙酸叔丁酯
[Teach you how to do mini-games] How to lay out the hands of Dou Dizhu?See what the UP master of the 250,000 fan game area has to say
Redis 持久化机制
Introduction to 3 d games beginners essential 】 【 modeling knowledge
第四届“传智杯”全国大学生IT技能大赛(初赛A组) 补题
电脑为什么会蓝屏的原因
Today's bug, click on the bug that the Windows dynamic wallpaper disappears in the win10 taskbar, and no solution has been found yet.