如何统计岛屿的数量和面积

在C++中统计岛屿的数量和面积通常是指处理二维网格（比如模拟地图）中的连通组件问题。岛屿可以被看作是网格中的连通组件，而面积则是由连通组件中的单元格数量决定的。

解决这个问题的一个常见算法是深度优先搜索（DFS）。以下是使用DFS统计岛屿数量和面积的步骤：

1. 遍历整个网格。
2. 当找到一个陆地单元格时，使用DFS从这个单元格开始遍历所有相连的陆地单元格。
3. 对于每次DFS调用，岛屿数量加一，并且每次访问一个陆地单元格，就将面积加一。
4. 将所有岛屿的面积累加起来，就能得到总面积。

下面是实现该算法的C++代码示例：

#include <vector>

void dfs(std::vector<std::vector<int>>& grid, int r, int c, int& area) {
    int nr = grid.size();
    int nc = grid[0].size();
    
    // 标记当前单元格为已访问
    grid[r][c] = 0; // 假设1表示陆地，0表示水
    area++; // 面积增加
    
    // 访问所有方向的相邻单元格
    static const int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (const auto& dir : directions) {
        int newR = r + dir[0], newC = c + dir[1];
        // 检查坐标是否在网格范围内，以及是否是陆地且未被访问过
        if (newR >= 0 && newR < nr && newC >= 0 && newC < nc && grid[newR][newC] == 1) {
            dfs(grid, newR, newC, area); // 递归访问
        }
    }
}

int numIslands(std::vector<std::vector<char>>& grid) {
    if (grid.empty()) return 0;
    
    int num_islands = 0;
    int nr = grid.size();
    int nc = grid[0].size();
    
    for (int r = 0; r < nr; ++r) {
        for (int c = 0; c < nc; ++c) {
            if (grid[r][c] == '1') { // 假设'1'表示陆地
                int area = 0;
                dfs(grid, r, c, area);
                // 打印每个岛屿的面积
                std::cout << "Island area: " << area << std::endl;
                num_islands++; // 岛屿数量增加
            }
        }
    }
    
    return num_islands;
}

int main() {
    std::vector<std::vector<char>> grid = {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };
    
    int num_islands = numIslands(grid);
    std::cout << "Total number of islands: " << num_islands << std::endl;
    
    return 0;
}

这段代码中，`numIslands` 函数遍历整个网格，当遇到陆地（假设用字符'1'表示）时，会调用`dfs`函数。`dfs`函数执行深度优先搜索，计算一个岛屿的面积并递归地访问所有相邻的陆地单元格。每次调用`dfs`函数都会增加岛屿数量，并输出该岛屿的面积。最后，`numIslands`函数返回所有岛屿的总数量。

请注意，这个例子中的`dfs`函数并没有显式返回值，而是通过引用参数`area`来计算岛屿面积。在实际应用中，你可能需要根据具体需求来调整这些细节。