从 695. 岛屿的最大面积 入手深度优先搜素DFS
2023-04-18 15:24:11 时间
一、什么是深度优先遍历(DFS)
以“深度”为第一关键词,每次都沿路径到不能再前进时,才退回到最近的岔路口,然后继续按同样的逻辑搜索。
二、题目与解答
题目:
Leetcode 695. 岛屿的最大面积
解答思路:
首先要遍历数组,当发现(i,j)对应为陆地时,进行如下步骤:
(1)递归解法
递归解法最重要的是首先要确定递归边界。(设计递归函数时,我们必须为它设置一个结束递归的“出口”,否则函数会一直调用自身(死循环),直至运行崩溃。)
该题有两个递归边界:
一个是矩阵尺寸限制,
一个是碰到了水域
一般来说,深度优先搜索类型的题可以分为主函数和辅函数,
主函数用于遍历所有的搜索位置,判断是否可以开始搜索,如果可以即在辅函数进行搜索。
辅函数则负责深度优先搜索的递归调用
本题中主函数为:int maxAreaOfIsland(vector<vector<int>>& grid);
辅函数为:int LandDFS(vector<vector<int>>& grid, int i, int j); 其中i, j 代表当前坐标。
class Solution { public: // 辅函数 int LandDFS(vector<vector<int>>& grid, int i, int j) { // 在矩阵尺寸范围内 if((i < grid.size()) && (i >= 0) && (j < grid[0].size()) && (j >= 0)) { if (grid[i][j] == 0) { // 碰到水 return 0; } else { grid[i][j] = 0; return 1 + LandDFS(grid, i-1, j) + LandDFS(grid, i+1, j) + LandDFS(grid, i, j-1) + LandDFS(grid, i, j+1); } } else { return 0; } } // 主函数 int maxAreaOfIsland(vector<vector<int>>& grid) { int ans = 0; for (int i = 0; i < grid.size(); i++) { for (int j = 0; j < grid[0].size(); j++) { ans = max(ans, LandDFS(grid, i, j)); // 这里LandDFS(grid, i, j)返回的是含(i,j)的岛屿的面积 } } return ans; } };
(2)栈解法
我们也可以使用栈(stack)实现深度优先搜索,但因为栈与递归的调用原理相同,而递归相对便于实现,因此刷题时推荐使用递归式写法,同时也方便进行回溯(见下节)。
不过在实际工程上,直接使用栈可能才是最好的选择,一是因为便于理解,二是更不易出现递归栈满的情况。
class Solution { private: vector<int> direction {-1, 0, 1, 0, -1}; // 每相邻两位即为上下左右四个方向之一 public: int maxAreaOfIsland(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); int localArea, area = 0, x, y; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j]) { // 进入岛屿 localArea = 1; grid[i][j] = 0; // 抹除 stack<pair<int, int>> IsLand; // 存放土地的堆栈 IsLand.push({i, j}); // 往堆中加入当前土地(该岛第一块土地) while (!IsLand.empty()) { auto [r, c] = IsLand.top(); // 从堆中取出元素,并访问 IsLand.pop(); // 从堆中取出元素,并访问 for (int k = 0; k < 4; k++) { // 上下左右 x = r + direction[k]; y = c + direction[k+1]; if ( x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) { ++localArea; grid[x][y] = 0; IsLand.push({x, y}); // 往堆中加入当前土地 ( (i,j)土地的领接土地节点 ) } } } } area = max(area, localArea); } } return area; } };
参考视频:
https://leetcode.cn/problems/max-area-of-island/solution/dao-yu-de-zui-da-mian-ji-by-leetcode-solution/
![](https://common.cnblogs.com/images/loading.gif)
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击