牛客网230100题岛屿的最大面积：深度优先搜索实战

一、问题重述

给定n*m的二进制矩阵，1代表陆地，0代表海洋，计算相连陆地组成的最大岛屿面积（相连仅限水平或垂直方向）

二、核心算法

采用深度优先搜索(DFS)进行连通区域标记：

1. 遍历矩阵每个点

2. 发现陆地时启动DFS

3. 搜索中标记已访问点避免重复计算

4. 比较记录最大面积

三、C++实现代码

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型vector<vector<>>
     * @return int整型
     */
    int maxAreaIsland(vector<vector<int> >& grid) {
        if (grid.empty()) return 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) { // 发现新陆地
                    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);
    }
};

四、关键点解析

1. 访问标记：将访问过的1改为2，避免重复计算

2. 递归终止条件：越界或遇到非陆地时返回0

3. 面积累加：当前点面积1 + 四个方向的扩展面积

五、算法可视化

示例矩阵：
1 1 0 0
1 0 1 1
0 1 0 1

搜索过程：
(0,0)触发DFS → 标记(0,0)(0,1)(1,0) → 面积3
(2,1)触发DFS → 标记(2,1)(1,2)(1,3)(2,3) → 面积4
最终结果：4