c++计算岛屿数量

在 C++ 中，计算岛屿数量是一个常见的算法问题，通常在二维网格（矩阵）中解决，其中 ‘1’ 表示陆地，‘0’ 表示水域。岛屿由水平或垂直相邻的陆地组成，我们需要计算岛屿的总数。

这个问题可以通过深度优先搜索（DFS）来解决。以下是实现的基本步骤：

1. 遍历每个单元格。
2. 当遇到 ‘1’（陆地）时，通过 DFS 遍历与之相邻的所有陆地单元格，并将它们标记为已访问。
3. 每次启动新的 DFS 都意味着找到了一个新岛屿，因此岛屿数量加一。
4. 继续遍历直到所有单元格都被检查过。

以下是 C++ 实现的示例代码：

#include <iostream>
#include <vector>

using namespace std;

void dfs(vector<vector<char>>& grid, int r, int c) {
    int nr = grid.size();
    int nc = grid[0].size();

    grid[r][c] = '0'; // 标记为已访问
    // 检查四个方向的相邻单元格
    if (r - 1 >= 0 && grid[r - 1][c] == '1') dfs(grid, r - 1, c);
    if (r + 1 < nr && grid[r + 1][c] == '1') dfs(grid, r + 1, c);
    if (c - 1 >= 0 && grid[r][c - 1] == '1') dfs(grid, r, c - 1);
    if (c + 1 < nc && grid[r][c + 1] == '1') dfs(grid, r, c + 1);
}

int numIslands(vector<vector<char>>& grid) {
    int nr = grid.size();
    if (!nr) return 0;
    int nc = grid[0].size();

    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {
        for (int c = 0; c < nc; ++c) {
            if (grid[r][c] == '1') {
                ++num_islands;
                dfs(grid, r, c);
            }
        }
    }

    return num_islands;
}

int main() {
    vector<vector<char>> grid = {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };

    cout << "Number of islands: " << numIslands(grid) << endl;

    return 0;
}

在这个例子中，dfs 函数用于深度优先搜索岛屿的所有部分，并将遍历过的陆地标记为 ‘0’。numIslands 函数遍历整个网格，当遇到一个未被访问的陆地单元格时，对其执行 DFS，并将岛屿数量加一。