最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

【环球新要闻】从 695. 岛屿的最大面积 入手深度优先搜素DFS

来源：博客园

一、什么是深度优先遍历（DFS）

以“深度”为第一关键词，每次都沿路径到不能再前进时，才退回到最近的岔路口，然后继续按同样的逻辑搜索。


(相关资料图)

二、题目与解答

题目：Leetcode 695.岛屿的最大面积

解答思路：

首先要遍历数组，当发现（i,j）对应为陆地时，进行如下步骤：

（1）递归解法

递归解法最重要的是首先要确定递归边界。

该题有两个递归边界：

一个是矩阵尺寸限制，

一个是碰到了水域

一般来说，深度优先搜索类型的题可以分为主函数和辅函数，

主函数用于遍历所有的搜索位置，判断是否可以开始搜索，如果可以即在辅函数进行搜索。

辅函数则负责深度优先搜索的递归调用

本题中主函数为：int maxAreaOfIsland(vector>& grid);

辅函数为：int LandDFS(vector>& grid, int i, int j); 其中i, j 代表当前坐标。

class Solution {public:    // 辅函数    int LandDFS(vector>& 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>& 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 direction {-1, 0, 1, 0, -1};  // 每相邻两位即为上下左右四个方向之一public:    int maxAreaOfIsland(vector>& 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> 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/

关键词： 深度优先搜索 深度优先