给你一个大小为 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
岛屿问题
200.岛屿数量(medium)
463. 岛屿的周长(easy)
305.岛屿数量Ⅱ(hard)
827.最大人工岛(hard)
这一类岛屿问题大多可以使用DFS解决，即深度优先搜索(Depth-First-Search)，一般使用递归的方式实现。
思路
题目给了一个m*n的二维矩阵grid，来表示一片海洋中的岛屿，其中0表示海洋，1表示岛屿，我们需要返回岛屿的最大面积，这里的岛屿只能通过上下左右四个方向连接，对角是不算连接的。
可以使用深度优先搜索来得到每一片岛屿的面积从而确定最大面积。何为深度优先搜索呢，顾名思义就是逮住一个方向往里冲，对应树结构就是往一个子树最深处走，通常深度优先搜索是实现在树结构或者图结构上的，本题则是在网格结构上，对树进行DFS时只需递归根节点的每个子树，空指针则返回。
而网格结构中需要递归该点的上下左右四个方向，会出现重复访问的问题。比如我们访问到了一个点时对它进行四个方向的搜索，而每个和它相邻的点又会反过来访问它，所以我们要避免重复访问，需要在递归的过程中标记访问过的点来防止重复访问。
对应本题目，首先遍历数组中的每一个元素，如果它是0，说明它是水（废话），直接跳过，我们关心的是1，当我们找到1，递归该点的四个方向，返回该岛屿的面积，继续寻找下一个1，由于这里递归过的点都被标记了，所以已经查找过的岛屿不会被访问了，也可以称之为沉岛。
接下来讲一下递归的过程以及递归函数怎么实现，递归需要返回，这里求的是面积，所以返回索引对应元素岛屿的面积。
int dfs(int[][] grid, int x, int y)
有经验的coder在面对这种递归的时候肯定会想到索引越界问题，当我们递归四个方向时，某个方向越界了怎么办，这里采用的方法是先大胆的递归，之后再处理，不管越不越界，先递归了四个方向再说，真越界了的话在函数里处理呗，注意这里多了一句 grid[x][y] != 1 ，当递归到的点是水时，我们同样不需要管它，因为它对岛屿的面积没有贡献，此时返回面积为0。
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != 1) { return 0; }
接下来需要定义一个变量来保存岛屿面积int num = 1;为什么它的初始值为1呢，因为如果越过了上面的判断，说明该点肯定是未访问过的一个陆地，所以面积自然为1咯，访问过该点后将该点标记为已访问 grid[x][y] = 2 ;，这里很多题解都会把这个点置0，变成水，在本题目中虽然可以这样做，但是在更多要求更复杂的题目中就无法分辨这个点究竟是访问过的还是本来就是水。
然后就是经典递归环节了，递归访问该节点的上下左右四个方向，并将返回值加到num上，最后返回num。
完整代码如下：
class Solution { public int maxAreaOfIsland(int[][] grid) { int n = grid.length; int m = grid[0].length; int res = 0; //初始化结果为0 for (int i = 0; i < n; i++) { //遍历每一个元素 for(int j = 0;j < m; j++) { if (grid[i][j] == 1) { //当前元素为1时才需要访问它 res = Math.max(res, dfs(grid, i, j)); //递归访问岛屿，每次得到最大的面积 } } } return res; } int dfs(int[][] grid, int x, int y) { //当前索引越界或者元素已经被访问过或者元素为0时直接返回0 if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != 1) { return 0; } int num = 1; //进入这一步说明当前访问的元素为1且为被访问过，初始化岛屿面积为1 grid[x][y] = 2; //然后将该岛屿标记为已访问 num += dfs(grid, x - 1, y); //递归访问当前节点的左边，并将返回结果相加 num += dfs(grid, x + 1, y); //右边 num += dfs(grid, x, y - 1); //下边 num += dfs(grid, x, y + 1); //上边 return num; //返回该节点和相邻合法节点面积 } }
原文：https://leetcode.cn/problems/max-area-of-island/solution/by-nice-hermann9a2-tmjx/
Original: https://www.cnblogs.com/liangren-na/p/16437611.html
Author: 良人呐
Title: 695.岛屿的最大面积
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/619851/
转载文章受原作者版权保护。转载请注明原作者出处！