当前位置:网站首页>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;
}
}
}
};
边栏推荐
- idea汉化教程[通俗易懂]
- LeetCode·26.删除有序数组中的重复项·双指针
- When selecting a data destination when creating an offline synchronization node - an error is reported in the table, the database type is adb pg, what should I do?
- We used 48h to co-create a web game: Dice Crush, to participate in international competitions
- The servlet mapping path matching resolution
- 7-2 乒乓人训练大师(双指针)
- 水溶性合金量子点纳米酶|CuMoS纳米酶|多孔硅基Pt(Au)纳米酶|[email protected]纳米模拟酶|PtCo合金纳米粒子
- RS-485多主机通信的组网方式评估
- YOLOv3 SPP源码分析
- argparse——命令行参数解析
猜你喜欢
【毕业设计】基于STM32的天气预报盒子 - 嵌入式 单片机 物联网
转铁蛋白(TF)修饰紫杉醇(PTX)脂质体(TF-PTX-LP)|转铁蛋白(Tf)修饰姜黄素脂质体
端口探测详解
多种深度模型实现手写字母MNIST的识别(CNN,RNN,DNN,逻辑回归,CRNN,LSTM/Bi-LSTM,GRU/Bi-GRU)
第15章_锁
[email protected] NPs)"/>
转铁蛋白修饰蛇床子素长循环脂质体/负载三七皂苷R1的PEG-PLGA纳米粒([email protected] NPs)
优化是一种习惯●出发点是'站在靠近临界'的地方
Common ports and services
子域名收集&Google搜索引擎语法
DefaultSelectStrategy NIOEventLoop执行策略
随机推荐
云渲染的应用正在扩大,越来越多的行业需要可视化服务
怎么完全卸载赛门铁克_Symantec卸载方法,赛门铁克卸载「建议收藏」
从 GAN 到 WGAN
redis 事件
越折腾越好用的 3 款开源 APP
DefaultSelectStrategy NIOEventLoop执行策略
7-2 乒乓人训练大师(双指针)
【毕业设计】基于Stm32的智能疫情防控门禁系统 - 单片机 嵌入式 物联网
365天挑战LeetCode1000题——Day 053 求解方程 解析 模拟
「POJ 3666」Making the Grade 题解(两种做法)
【Knowledge Sharing】What is SEI in the field of audio and video development?
CAS:190598-55-1_Biotin sulfo-N-hydroxysuccinimide ester生物素化试
L2-035 完全二叉树的层序遍历
spark学习笔记(九)——sparkSQL核心编程-DataFrame/DataSet/DF、DS、RDD三者之间的转换关系
cordova 安装错误 Command failed: powershell 解决方法
Introduction to 3 d games beginners essential 】 【 modeling knowledge
When selecting a data destination when creating an offline synchronization node - an error is reported in the table, the database type is adb pg, what should I do?
whois信息收集&企业备案信息
【自然语言处理】【向量表示】PairSupCon:用于句子表示的成对监督对比学习
laya打包发布apk