题目描述补充

题目：最大连通面积

给定一个二维网格（矩阵），其中的每个单元格可以是1（表示土地）或0（表示水域）。土地单元格与其上下左右相邻的同为土地的单元格被视为连通的。要求编写一个算法，找出网格中所有土地单元格形成的最大连通区域的面积，并返回该面积。

示例

输入网格：

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 1 1 1

输出：4（最大连通区域的面积为4）

解题思路

这个问题可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。算法的基本思想是遍历整个网格，每当遇到一个值为1的单元格时，就启动一次搜索，计算当前连通区域的面积，并更新最大面积。为了避免重复计算，可以将已访问过的土地单元格标记为已访问（例如，将值改为另一个非0非1的值）。

PHP 示例代码

function maxAreaOfIsland($grid) {
    $rows = count($grid);
    if ($rows == 0) return 0;
    $cols = count($grid[0]);
    $maxArea = 0;

    function dfs(&$grid, $row, $col, $rows, $cols) {
        if ($row < 0 || $row >= $rows || $col < 0 || $col >= $cols || $grid[$row][$col] != 1) {
            return 0;
        }
        $grid[$row][$col] = -1; // 标记为已访问
        $area = 1;
        $area += dfs($grid, $row - 1, $col, $rows, $cols); // 上
        $area += dfs($grid, $row + 1, $col, $rows, $cols); // 下
        $area += dfs($grid, $row, $col - 1, $rows, $cols); // 左
        $area += dfs($grid, $row, $col + 1, $rows, $cols); // 右
        return $area;
    }

    for ($i = 0; $i < $rows; $i++) {
        for ($j = 0; $j < $cols; $j++) {
            if ($grid[$i][$j] == 1) {
                $maxArea = max($maxArea, dfs($grid, $i, $j, $rows, $cols));
            }
        }
    }

    return $maxArea;
}

Python 示例代码

def maxAreaOfIsland(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    max_area = 0
    
    def dfs(row, col):
        nonlocal max_area
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] != 1:
            return 0
        grid[row][col] = 0  # 标记为已访问
        area = 1
        area += dfs(row - 1, col)  # 上
        area += dfs(row + 1, col)  # 下
        area += dfs(row, col - 1)  # 左
        area += dfs(row, col + 1)  # 右
        return area
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                max_area = max(max_area, dfs(i, j))
                
    return max_area

JavaScript 示例代码

function maxAreaOfIsland(grid) {
    if (!grid.length) return 0;
    
    const rows = grid.length;
    const cols = grid[0].length;
    let maxArea = 0;
    
    function dfs(row, col) {
        if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] !== 1) {
            return 0;
        }
        grid[row][col] = -1; // 标记为已访问
        let area = 1;
        area += dfs(row - 1, col); // 上
        area += dfs(row + 1, col); // 下
        area += dfs(row, col - 1); // 左
        area += dfs(row, col + 1); // 右
        return area;
    }
    
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === 1) {
                maxArea = Math.max(maxArea, dfs(i, j));
            }
        }
    }
    
    return maxArea;
}

码小课网站中有更多相关内容分享给大家学习，涵盖了算法、数据结构、编程技巧等多个方面，欢迎访问学习。