刷题44——岛屿的最大面积

78.岛屿的最大面积

题目链接

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-area-of-island

题目描述

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

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

示例 1:

[[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:

[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。

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

关键技术

DFS(深度优先搜索)

题目分析

1. 在grid边界内搜索，若超出grid边界，或者搜索的位置为0，返回0，设置x，y为岛屿边界，即if(i<0 || i>=x || j<0 ||j>=y || grid[i][j] == 0) return 0;
2. 最大的岛屿面积：在grid内指定方向（水平或者垂直）上最多的连续的1的个数；
3. 在grid内搜索时遵循规则从当前位置四个方向搜索：上、下、左、右，即i-1,i+1,j-1,j+1;
4. 若搜索到1，岛屿面积+1（num+1)，并把位置赋值0(grid[i][j] = 0)，再进行下一次搜索；
5. 求岛屿最大面积：max = Math.max(max,numPath(grid,i,j,x,y));

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
    let x = grid.length;
    let y = grid[0].length;
    let max = 0;
    for(let i=0;i<x;i++){
        for(let j=0;j<y;j++){
            if(grid[i][j] == 1){
                max = Math.max(max,numPath(grid,i,j,x,y));
            }
        }
    }
    return max;
};
function numPath(grid,i,j,x,y){
    if(i<0 || i>=x || j<0 ||j>=y || grid[i][j] == 0) return 0;
    let num = 1;
    grid[i][j] = 0;
    num += numPath(grid,i+1,j,x,y);
    num += numPath(grid,i-1,j,x,y);
    num += numPath(grid,i,j+1,x,y);
    num += numPath(grid,i,j-1,x,y);
    return num;
}