源题目

https://leetcode-cn.com/problems/max-area-of-island/

695. 岛屿的最大面积

难度中等534
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 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。

class Solution {
    /**
     * @param Integer[][] $grid
     * @return Integer
     */
    function maxAreaOfIsland($grid) {
        $ans = 0;
        $len = count($grid);
        $len2 = count($grid[0]);
        for($i = 0; $i < $len; $i ++){
            for($j = 0; $j < $len2; $j ++){
                // 若该位置为岛屿, 则开始计算该岛屿的面积
                if ($grid[$i][$j] == 1) {
                    $ans = max($ans, $this->dfs($i, $j, $grid));
                }
            }
        }
        return $ans;
    }
    function dfs($i, $j, &$grid){
        $len = count($grid);
        $len2 = count($grid[0]);
        if ($i < 0 || $i >= $len || $j < 0 || $j >= $len2 || $grid[$i][$j] == 0) {
            return 0;
        }
        // 避免重复计算
        $grid[$i][$j] = 0;
        // 初始面积为 1
        $num = 1;
        $num += $this->dfs($i + 1, $j, $grid);//向右
        $num += $this->dfs($i - 1, $j, $grid);//向左
        $num += $this->dfs($i, $j + 1, $grid);//向下
        $num += $this->dfs($i, $j - 1, $grid);//向上
        return (int)$num;
    }
}