当前位置：首页 > 牛客 > 牛客网230100题岛屿最大面积：深度优先搜索（DFS）算法解析

牛客网230100题岛屿最大面积：深度优先搜索（DFS）算法解析

2天前

一、题目解读

本题要求在一个由0和1组成的二维网格中，计算岛屿的最大面积。岛屿由相邻的1（陆地）组成，相邻位置包括上下左右四个方向。网格中的0代表海洋，岛屿不可跨越海洋。需返回所有岛屿中面积最大的值。若网格为空，则返回0。

二、解题思路

采用深度优先搜索（DFS）算法。遍历网格每个位置，当遇到陆地（grid[i][j] == 1）时，启动DFS递归计算当前岛屿面积，同时标记已访问的陆地为2，避免重复计算。通过遍历所有陆地，记录最大面积值。关键在于利用递归遍历岛屿的连通块，并累加面积。

三、解题步骤

1. 初始化：若网格为空，直接返回0。记录网格行数（rows）和列数（cols），初始化最大面积max_area为0。

2. 遍历网格：双层循环遍历每个位置(i, j)，若grid[i][j] == 1，调用dfs计算当前岛屿面积，更新max_area。

3. 递归计算面积（dfs）：

○ 边界检查：若坐标越界或当前位置为海洋/已访问（grid[i][j]!= 1），返回0。

○ 标记已访问：将当前位置标记为2（避免重复计算）。

○ 递归向四周扩散：递归调用dfs计算上下左右四个方向的连通陆地面积，并累加。

○ 返回当前位置面积（1）+ 四周面积之和。

四、代码及注释

class Solution {
public:
    int maxAreaIsland(vector<vector<int>>& grid) {
        if (grid.empty()) return 0; // 空网格直接返回0
        int max_area = 0;          // 初始化最大面积
        rows = grid.size();        // 记录行数
        cols = grid[0].size();     // 记录列数

        for (int i = 0; i < rows; ++i) {  // 遍历行
            for (int j = 0; j < cols; ++j) { // 遍历列
                if (grid[i][j] == 1) { // 发现陆地，调用DFS
                    max_area = max(max_area, dfs(grid, i, j)); // 更新最大面积
                }
            }
        }
        return max_area;
    }

private:
    int rows, cols; // 全局变量记录行列数
    int dfs(vector<vector<int>>& grid, int i, int j) {
        // 边界 + 海洋/已访问检查
        if (i < 0 || j < 0 || i >= rows || j >= cols || grid[i][j]!= 1) 
            return 0;
        grid[i][j] = 2; // 标记已访问
        return 1 + dfs(grid, i+1, j) + dfs(grid, i-1, j) // 向下、向上递归
               + dfs(grid, i, j+1) + dfs(grid, i, j-1); // 向右、向左递归
    }
};