一 、什么是深度优先遍历（DFS）
以“深度 ”为第一关键词 ，每次都沿路径到不能再前进时 ，才退回到最近的岔路口 ，然后继续按同样的逻辑搜索 。
二 、题目与解答
题目：
Leetcode 695.岛屿的最大面积
解答思路：
首先要遍历数组 ，当发现（i,j）对应为陆地时 ，进行如下步骤：
（1）递归解法
递归解法最重要的是首先要确定递归边界 。
该题有两个递归边界：
一个是矩阵尺寸限制 ，
一个是碰到了水域
一般来说 ，深度优先搜索类型的题可以分为主函数和辅函数 ，
主函数用于遍历所有的搜索位置 ，判断是否可以开始搜索 ，如果可以即在辅函数进行搜索 。
辅函数则负责深度优先搜索的递归调用
本题中主函数为：int maxAreaOfIsland(vector<vector<int>>& grid);
辅函数为：int LandDFS(vector<vector<int>>& grid, int i, int j); 其中i, j 代表当前坐标 。
（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/
声明：本站所有文章 ，如无特殊说明或标注 ，均为本站原创发布 。任何个人或组织 ，在未征得本站同意时 ，禁止复制 、盗用 、采集 、发布本站内容到任何网站 、书籍等各类媒体平台 。如若本站内容侵犯了原著者的合法权益 ，可联系我们进行处理 。
