LeetCode C++ 200. Number of Islands【DFS/BFS】中等
发布日期:2021-07-01 02:56:58
浏览次数:2
分类:技术文章
本文共 2510 字,大约阅读时间需要 8 分钟。
Given an m x n
2d grid
map of '1'
s (land) and '0'
s (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"]]Output: 1
Example 2:
Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"]]Output: 3
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]
is'0'
or'1'
.
题意:给出一个由 '1'
(陆地)和 '0'
(水)组成的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
解法1 DFS
对二维网格中的每个值为 1
且不为已知岛屿的单元格进行DFS:
class Solution { private: vector> vis; int m, n; void dfs(const vector >& grid, int i, int j) { if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0' || vis[i][j]) return; vis[i][j] = true; dfs(grid, i + 1, j); dfs(grid, i - 1, j); dfs(grid, i, j - 1); dfs(grid, i, j + 1); }public: int numIslands(vector >& grid) { m = grid.size(), n = grid[0].size(); int islands = 0; vis.resize(m, vector (n, false)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (vis[i][j] == false && grid[i][j] == '1') { dfs(grid, i, j); ++islands; } } } return islands; }};
执行效率如下:
执行用时:32 ms, 在所有 C++ 提交中击败了74.97% 的用户内存消耗:10 MB, 在所有 C++ 提交中击败了29.30% 的用户
解法2 BFS
class Solution { public: int numIslands(vector>& grid) { int m = grid.size(), n = grid[0].size(), islands = 0; int Moves[][2] = { 0, 1, 0, -1, 1, 0, -1, 0}; vector > vis(m, vector (n, false)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (vis[i][j] == false && grid[i][j] == '1') { ++islands; //岛屿数量+1 queue > q; //BFS这个岛屿 q.push({ i, j}); vis[i][j] = true; while (!q.empty()) { pair t = q.front(); q.pop(); for (int b = 0; b < 4; ++b) { //遍历四个方向 int tx = t.first + Moves[b][0], ty = t.second + Moves[b][1]; if (tx >= 0 && tx < m && ty >= 0 && ty < n && grid[tx][ty] == '1' && !vis[tx][ty]) { q.push({ tx, ty}); vis[tx][ty] = true; } } } } } } return islands; }};
执行用时和内存消耗如下:
执行用时:32 ms, 在所有 C++ 提交中击败了74.28% 的用户内存消耗:10.6 MB, 在所有 C++ 提交中击败了10.55% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/110082507 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月15日 16时15分08秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
通过 ulimit 改善系统性能
2019-05-02
Linux中的tty,pty与pts以及/dev下各种tty设备
2019-05-02
gdbserver远程调试
2019-05-02
openlog、syslog和closelog函数
2019-05-02
syslog详解
2019-05-02
Linux下shell的远程协助
2019-05-02
fastcgi中的多线程使用
2019-05-02
实现spawn-fcgi的守护监控功能
2019-05-02
JavaScript window.location对象
2019-05-02
业务流程图的绘制流程分享(一)
2019-05-02
W25Q64Flash芯片
2019-05-02
STM32唯一ID(Unique Device ID)的读取方法
2019-05-02
rtthread 函数学习
2019-05-02
关于RT-Thread调度器锁
2019-05-02
使用j_Flash合并bin文件
2019-05-02
STM32 备份域(备份寄存器、备份SRAM)详解及数据丢失问题处理
2019-05-02
MicroPython入门指南
2019-05-02
x265-1.7版本-common/bitstream.h注释
2019-05-02
x265-1.7版本-common/frame.h注释
2019-05-02
x265-1.7版本-common/framedata.cpp注释
2019-05-02