BFS 力扣 200.岛屿数量 深度操作系统Deepin V20正式版 2020-09-13 【OS】Bankers Algorithm 用于调用的参数太少/写入位置时发生冲突/检测到无效的异常处理程序例程 后渗透之各种维持权限的后门原理即利用 MIPS Branch Target Buffer动态分支预测(BTB) Oracle实战优化:INSERT ALL关键字的应用 Linux中MySQL数据库的使用②-----数据的基本操作 理论+实验——MySQL备份与恢复 MySQL常用数据库函数 MySQL 备份与恢复(完全备份恢复--增量备份恢复+案例演示) MySQL之基础总结部分 Oracle实战优化:递归+分析函数+OLAP函数的应用 Linux中MySQL数据库的使用③-----编码和基本数据类型 理论+实验:MySQL备份与恢复(完整备份、增量备份) “数”聚永川 “智”引未来——永川区大数据智能化产业发展强劲 从一款防疫App感受新加坡大数据智能化气息 “数”聚永川“智”引未来——永川区大数据智能化产业发展强劲 从连接量变到数据质变 物联网将二次爆发 重磅发布!猎芯半导体首创全球最小支持5G物联网的多模多频射频PA芯片 从精准授信到助企惠民,江苏银行物联网金融派上大用场 Python Selenium UI自动化_WebDriver元素_8大定位方式+总结(持续更新完善) Python中的继承、抽象基类和接口 Datawhale学习笔记【阿里云天池 金融风控-贷款违约预测】task1 赛题理解 Pytorch - torchvision计算机视觉工具库 linux 重点笔记 Ubuntu18.04安装ROS Melodic(一路到站型) 小甲鱼笔记:数据结构——线性表(一)线性表的顺序存储结构,线性表顺序存储结构的增,删,插入元素操作 实战比特币脚本编程(1) JAVA WEB DAY 01_Tomcat & Servlet Java基础算法之堆排序(Heap Sort) synchronized批量重偏向与批量撤销 终于等到了!阿里P8历时九个月整理,Java面试宝典,核心知识点笔记在此 “数字心脏”动态解析消费密码,国家级消费市场大数据联合实验室在上海先行先试 全世界运行着大约230亿台物联网设备,安全问题如何解? 物联网产业园&thinkplus解决方案中心国学讲座如期而至 都是程序员,凭什么他能站在鄙视链的顶端? 猛男必看!去小红书做程序员是种什么体验 drozer提示[Errno 2] No such file or directory 【STM32】NB-iOT BC35-G模块 AT指令应用设计指导(附代码) 【北京迅为】i.MX6ULL终结者编译LED汇编程序 Linux系统读写网卡PHY寄存器工具 洛谷:P1226 【模板】快速幂||取余运算(分治,数学) 【2020顶会KDD】AutoST:面向时空预测的高效神经网络学习模型 C/C++实现并查集disjoint_set的模板(带路径压缩优化) 实现一个百万级推送服务,除了它,还有谁 “健康守护者”——STM32标准库和HAL库的比较 程序员被公司辞退12天后,前领导要求回公司讲清代码,结果懵了 RTTR实现C++反射(1)集成rttr库
您的位置:首页 >计算机基础 >

BFS 力扣 200.岛屿数量

力扣 200.岛屿数量

给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

示例 1: 输入:

[['1','1','1','1','0'],['1','1','0','1','0'],['1','1','0','0','0'],['0','0','0','0','0']]

输出:

1

示例 2:

输入:

[['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']]

输出:

3

解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

思路: 遍历整个二维网格,遇到岛屿时将坐标插入队列中,然后从队首开始逐步搜索,搜索后弹出对首,遇到陆地便插入队列,并标记其坐标,队列为空后岛屿数量加一。 代码:

class Solution{public:int numIslands(vector<vector<char>> &grid){int b = grid.size();if (!b)return 0;int a = grid[0].size();int ans = 0;for (int i = 0; i < b; i++){for (int j = 0; j < a; j++){if (grid[i][j] == '1'){ans++;grid[i][j] = '0';queue<pair<int, int>> ngb;ngb.push({i, j});while (!ngb.empty()){auto x = ngb.front();ngb.pop();int row = x.first, col = x.second;if (row - 1 >= 0 && grid[row - 1][col] == '1'){ngb.push({row - 1, col});grid[row - 1][col] = '0';}if (row + 1 < b && grid[row + 1][col] == '1'){ngb.push({row + 1, col});grid[row + 1][col] = '0';}if (col - 1 >= 0 && grid[row][col - 1] == '1'){ngb.push({row, col - 1});grid[row][col - 1] = '0';}if (col + 1 < a && grid[row][col + 1] == '1'){ngb.push({row, col + 1});grid[row][col + 1] = '0';}}}}}return ans;}};

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。