关于6.2深度优先搜索 695.Max Area of Island 第一种递归解法

[lei-hsia]

在您的书 P26/143的上半页写到: "一种是先判定是否越界,只有在合法的情况下才进行下一步搜索(即判断放在调用 递归函数前)", 对应的代码为:

// 主函数
int maxAreaOfIsland(vector<vector<int>>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    int max_area = 0;
    for (int i = 0; i < grid.size(); ++i) {
       for (int j = 0; j < grid[0].size(); ++j) {
           if (grid[i][j] == 1) {
              max_area = max(max_area, dfs(grid, i, j));
           }
} }
    return max_area;
}
// 辅函数
int dfs(vector<vector<int>>& grid, int r, int c) {
    if (grid[r][c] == 0) return 0;
    grid[r][c] = 0;
    int x, y, area = 1;
    for (int i = 0; i < 4; ++i) {
       x = r + direction[i], y = c + direction[i+1];
       if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()) {
           area += dfs(grid, x, y);
       }
}
    return area;
}

由于在主函数中已经进行了if (grid[i][j] == 1)判断才能进入递归，所以我之前想，在helper函数中第一行if (grid[r][c] == 0) return 0;是否多余，删除之后提交出现StackOverflow的问题。

这里就不是很理解了，如果是主函数中先判断，通过条件之后才递归，为什么在helper函数中仍然需要判断？(如果是不管三七二十一搜索，那么helper中肯定需要判断，这个好理解)

希望您这里能够做出详细一点的解释。我想应该不止我一个有这个问题

[triangleCZH]

@lei-hsia 在主函数的if ()不是唯一进入递归的方法，辅函数里面也有dfs(grid, x, y)， 那么这个辅函数调用自己之前也需要检测 == 0的case。如果不这么做的话，会有以下问题： 假设[[1,1,1,1,1]]，我们从dfs(grid, 0,0)开始，他会进入递归去做dfs(grid, 0, 1)，dfs(grid,0,1)反过来又会去做dfs(grid,0,0)，这里只有在辅函数内部检测过 grid[0][0] == 0 才能停下，否则两个连续的island会无限相互call。辅函数中把grid[r][c] 先设置成0就是为了标记已检测的岛屿，配合if grid[][] == 0防止被二次检测

[lei-hsia]

赞👍. 懂了，其实最重要的地方就是 dfs中也会调用dfs