C++助力探险家：计算神秘岛屿独立领地数量

要计算岛屿上独立领地的数量，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来遍历网格并标记已访问的陆地区域。每当我们遇到一个未被访问的陆地区域时，我们就启动一次搜索，并将所有与该陆地区域相连的其他陆地区域标记为已访问。这样，每次启动搜索时，我们都找到了一个新的领地。 下面是使用C++编写的解决方案，它使用DFS算法来计算独立领地的数量： ```cpp #include <iostream> #include <vector> using namespace std; // 定义DFS函数，用于遍历并标记一个领地中的所有陆地区域 void dfs(vector<vector<int>>& grid, int i, int j) { // 检查边界条件和当前区域是否为陆地 if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0) { return; } // 将当前区域标记为已访问（例如，用-1表示） grid[i][j] = -1; // 递归地访问相邻的陆地区域 dfs(grid, i - 1, j); // 上 dfs(grid, i + 1, j); // 下 dfs(grid, i, j - 1); // 左 dfs(grid, i, j + 1); // 右 } int numIslands(vector<vector<int>>& grid) { int count = 0; int n = grid.size(); int m = grid[0].size(); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { // 如果遇到一个未被访问的陆地区域，启动一次DFS搜索 if (grid[i][j] == 1) { ++count; dfs(grid, i, j); } } } return count; } int main() { int n, m; cin >> n >> m; vector<vector<int>> grid(n, vector<int>(m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> grid[i][j]; } } int result = numIslands(grid); cout << result << endl; return 0; } ``` 代码说明 1. 输入处理： - 首先读取岛屿网格的行数 `n` 和列数 `m`。 - 然后读取 `n` 行，每行 `m` 个整数，表示网格中每个区域的状态（0 或 1）。 2. DFS 函数： - `dfs` 函数用于递归地访问和标记一个领地中的所有陆地区域。 - 边界条件和当前区域是否为陆地是递归的终止条件。 - 将当前区域标记为已访问（例如，用 -1 表示）。 - 递归地访问当前区域的上下左右四个相邻区域。 3. 计算领地数量： - `numIslands` 函数遍历整个网格。 - 每当遇到一个未被访问的陆地区域时，启动一次 DFS 搜索，并将领地数量加一。 4. 输出结果： - 最后输出独立领地的数量。 额外需要注意的逻辑点 1. 边界条件：在DFS过程中，需要仔细处理边界条件，确保不会访问到网格之外的区域。 2. 状态标记：使用一种方法（例如将陆地标记为-1）来记录已访问过的区域，以避免重复计算。 3. 输入验证：可以添加输入验证逻辑来确保输入的网格是有效的（例如，确保 `n` 和 `m` 大于0，输入的数据符合预期的格式）。 ######[AI写代码神器 | 912点数解答 | 2025-03-16 19:22:31]