面积最大的岛屿是哪个岛屿（从 695. 岛屿的最大面积 入手深度优先搜素DFS）
导读：一、什么是深度优先遍历（DFS）...
一、什么是深度优先遍历（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/
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！