当前位置： 面试刷题>> 最大连通面积 (经典算法题500道)
### 题目描述补充
题目：**最大连通面积**
给定一个二维网格（矩阵），其中的每个单元格可以是`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 示例代码
```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 示例代码
```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 示例代码
```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;
}
```
**码小课**网站中有更多相关内容分享给大家学习，涵盖了算法、数据结构、编程技巧等多个方面，欢迎访问学习。