695. 岛屿的最大面积-蒲公英云

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

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

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

在这里插入图片描述

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] 为 0 或 1

思路（DFS）：

在这里插入图片描述

广度优先搜索一层一层遍历，每一层得到的所有新节点，要用队列存储起来以备下一层遍历的时候再遍历。
而深度优先搜索在得到一个新节点时立即对新节点进行遍历：从节点 0 出发开始遍历，得到到新节点 6 时，立马对新节点 6 进行遍历，得到新节点 4；如此反复以这种方式遍历新节点，直到没有新节点了，此时返回。返回到根节点 0 的情况是，继续对根节点 0 进行遍历，得到新节点 2，然后继续以上步骤。

从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种可达性问题。

在程序实现 DFS 时需要考虑以下问题：

栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。

代码（Java）：

public class dfs_max_area {
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        int [][] grid = {
                {
    0,0,1,0,0,0,0,1,0,0,0,0,0},
                {
    0,0,0,0,0,0,0,1,1,1,0,0,0},
                {
    0,1,1,0,1,0,0,0,0,0,0,0,0},
                {
    0,1,0,0,1,1,0,0,1,0,1,0,0},
                {
    0,1,0,0,1,1,0,0,1,1,1,0,0},
                {
    0,0,0,0,0,0,0,0,0,0,1,0,0},
                {
    0,0,0,0,0,0,0,1,1,1,0,0,0},
                {
    0,0,0,0,0,0,0,1,1,0,0,0,0}
        };
        int num = maxAreaOfIsland(grid);
        System.out.println(num);
    }
    private static int m;
    private static int n;
    private static int [][] direction = {
    {
    0,1},{
    1,0},{
    -1,0},{
    0,-1}};
    public static int maxAreaOfIsland(int[][] grid) {
        if(grid == null || grid.length == 0) {
            return 0;
        }
        m = grid.length;
        n = grid[0].length;
        int maxArea = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                maxArea = Math.max(maxArea, dfs(grid, i, j));
            }
        }
        return maxArea;
    }
    private static int dfs(int[][] grid, int r, int c) {
        // TODO 自动生成的方法存根
        if(r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
            return 0;
        }
        grid[r][c] = 0;//标记已经访问
        int area = 1;
        for(int [] d: direction) {
    //只有四个方向可以走，类似于栈
            area += dfs(grid, r + d[0], c + d[1]);
        }
        return area;
    }
}