695. 岛屿的最大面积（DFS）

695. 岛屿的最大面积

• 题目
• 解题思路
• 代码

题目

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

解题思路

这题求岛屿最大面积，又要求岛屿要连续，其实就是可达性问题很明显要用DFS。

知道要用DFS了就去套DFS模板，具体细节看代码注释

代码

class Solution {
       public int maxAreaOfIsland(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int res = 0;//用来保存结果
        for (int r = 0; r < grid.length; r++) {//遍历每一行
            for (int c = 0; c < grid[0].length; c++) {//遍历每一列
                if (grid[r][c] == 1) {//只有发现了岛屿才开始扩展搜索，如果岛屿都没有发现，那就没有展开的必要
                    int area = DFS(grid, r, c);
                    res = Math.max(res, area);//对于本次循环来说res保存的是之前循环找到的最大岛屿数量，area是这一次找到的岛屿数量，  比较二者将最大的赋值给res，可以保证res一直是最大岛屿数量
                }
            }

        }
        return res;
    }

    public int DFS(int[][] grid, int r, int c) {
        if (!(0 <= r && r < grid.length
                && 0 <= c && c < grid[0].length)) {//超出了边缘，走不下去了
            return 0;
        }

        if (grid[r][c] != 1) {//不是岛屿也返回，因为岛屿要相连的1，一旦出现0就要返回
            return 0;
        }

        grid[r][c] = 0;//经过前面两个if筛选。可以确保正在遍历的这个值是岛屿（1），遍历过后为了避免再次遍历，就将它变成0，简称“沉岛”。【还可以建一个集合Visited用来保存遍历过的岛屿，但是这题没有要求不能修改原数组，为了节省空间我们就直接修改原数组为0】

        int area = 1;//正在遍历的值为1，是岛屿，所以岛屿数量至少为1.

        area += DFS(grid, r - 1, c);//向上遍历
        area += DFS(grid, r + 1, c);//向下遍历
        area += DFS(grid, r, c - 1);//向左遍历
        area += DFS(grid, r, c + 1);//向右遍历

        //上面四句area+=xxX;相当于把上下左右四个方向的岛屿数量全加起来了。
        return area;
    }
}