从 695. 岛屿的最大面积 入手深度优先搜素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 代表当前坐标。

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;
    }
};