Leetcode 200 Number of Islands 岛的个数

Leetcode 200 Number of Islands 岛的个数

01

题目描述:

给出一个2D的地图,由陆地(1)和水(0)组成,数出岛的个数.一个岛被水环绕并且与相邻的陆地连接.
你可以假设方阵的四周被水环绕.

02

题目分析:

采用广度优先遍历的方法还是很容易解决这个问题的

03

算法

1. 遍历每一个结点,如果某结点是陆地且未访问过,岛数目加1,修改未访问标志位,然后把该点放入队列中,以备扩展岛屿使用,进入2 2. 队列不为空时,取出点,然后尝试对其上下左右的四个点进行扩展,如果其邻点是陆地且未访问过,则修改标志位并入队列.第2步运行结束时一个新岛的扩展结束,回到1. 3. 1中提到的遍历结束时,程序结束.

注意:对每个节点都进行BFS计算

04

利用递归遍历

非递归方式

class Solution { public: /** 计算岛屿的个数 */ int numIslands(vector<vector<char> >& grid) { int count = 0, rows = grid.size(), cols = rows > 0 ? grid[0].size() : 0; if (rows == 0 || cols == 0) return count; // 记录是否访问过 vector<vector<bool> > visited(rows, vector<bool>(cols, false)); // 用于遍历某一个岛相连接的所有岛 queue<int> q; // 用于查看某结点四周的结点 int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; int x = 0, y = 0, xx = 0, yy = 0; /* 遍历所有结点 */ for (int i = 0; i < rows; ++i) for (int j = 0; j < cols; ++j) { if (grid[i][j] == '1' && !visited[i][j]) { // 如果一个结点是1且没有访问过,则为新的小岛 q.push(i); // 小岛入队列 q.push(j); visited[i][j] = true; // 修改访问标志 ++count; // 小岛数量加1 while (!q.empty()) { // 修改与当前小岛相连的所有点的标志位 x = q.front(); // 广度优先遍历 q.pop(); y = q.front(); q.pop(); for (int k = 0; k < 4; ++k) { // 遍历某点的上下左右4个点 xx = x + dx[k]; yy = y + dy[k]; if (xx < 0 || xx >= rows || yy < 0 || yy >= cols) continue; // 越界,跳过 if (grid[xx][yy] == '1' && !visited[xx][yy]) { // 如果未曾访问过,修改访问标志,并加到队列中 visited[xx][yy] = true; q.push(xx); q.push(yy); } } } } } return count; }

广度优先搜索总的查找效率为O(V+n)

本文分享自微信公众号 - 架构说(JiaGouS)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-09-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

如何用Map对象创建Set对象

Java中的Map和Set有不少相似之处。本文将分享一个把Map类转化成Set类的小技巧。

10310
来自专栏wOw的Android小站

[设计模式]之一:简单工厂模式

最近思考了一下这两年的工作:做Android的时候一直看Android知识,做iOS的时候一直学iOS的东西。其实看起来感觉这样没什么问题,但仔细想想,我发现自...

20210
来自专栏java一日一条

java中HashMap详解

通过HashMap、HashSet 的源代码分析其 Hash 存储机制 实际上,HashSet 和 HashMap 之间有很多相似之处,对于 HashSet ...

22920
来自专栏跟着阿笨一起玩NET

浅谈数据库设计技巧(上)(转)

转一篇他人写的数据库设计技巧,感觉也不一定都正确,开拓一下思路吧。 说到数据库,我认为不能不先谈数据结构。1996年,在我初入大学学习计算机...

28310
来自专栏黄Java的地盘

动态生成DOM元素的高度及行数获取与计算方法

在开发IM的项目过程中,经常会有出现一些需要计算DOM高度,然后超出若干行隐藏等需求。很多时候,需要计算高度的DOM元素都是动态生成的,我们无法在数据渲染前获取...

30820
来自专栏java一日一条

如何用Map对象创建Set对象

Java中的Map和Set有不少相似之处。本文将分享一个把Map类转化成Set类的小技巧。

10910
来自专栏林德熙的博客

大文件的存储和备份

大概这个算法是现在世界上最好的存储算法之一,原因是他的论文发在 SCI 上,现在还没有人写出一个比他好的算法。

1K20
来自专栏林德熙的博客

win 10 UWP 标签

本文主要翻译:http://visuallylocated.com/post/2015/02/20/Creating-a-WrapPanel-for-your-...

13720
来自专栏跟着阿笨一起玩NET

生成不重复的随机数算法

本文转载http://blog.csdn.net/zhoufoxcn/article/details/5825093#comments

56310
来自专栏林德熙的博客

俄罗斯方块

俄罗斯方块是一个很经典的游戏,做一个UWP俄罗斯方块没有什么用,我想说的是移植,把经典游戏移植到UWP。

17910

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励