695.岛屿的最大面积

一、题目

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

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

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

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

示例一：

输入：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 。

示例二：

输入：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

二、相关链接

题目链接：https://leetcode-cn.com/problems/max-area-of-island/
参考题解：https://leetcode-cn.com/problems/max-area-of-island/solution/biao-zhun-javadong-tai-gui-hua-jie-fa-100-by-mark-/

三、解题思路

解法：深度优先遍历
思路：
- 参考733.图像渲染
- 遍历数组，每次进行dfs，返回值判断最大值
- 岛屿相连的为1则是同一个岛屿，需要+1，并把该岛屿置为0(防止重复计算)

四、代码

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        //遍历m x n，遇到1的就遍历四个方向，遍历过的就重置为0，防止重新遍历到
        for(int m=0;m<grid.length;m++){
            for(int n=0;n<grid[m].length;n++) {
                //每遍历一次就判断是不是更大的岛屿
                maxArea = Math.max(maxArea, this.dfs(grid,m,n));
            }
        }

        return maxArea;
    }

    public int dfs(int[][] grid, int x, int y) {
        int area = 0;
        if(x<0 || y<0 || x>grid.length-1 || y>grid[0].length-1 || grid[x][y]!=1) {
            //该位置不是岛屿，返回0
            return 0;
        }

        //计算岛屿面积，并重置grid
        area+=1;
        grid[x][y] = 0;

        //看看有没有(上下左右)连接的岛屿
        area += this.dfs(grid,x-1,y);
        area += this.dfs(grid,x+1,y);
        area += this.dfs(grid,x,y-1);
        area += this.dfs(grid,x,y+1);

        return area;
    }
}