方馆长新发现神秘岛屿！C++程序助力计算领地数量

# 岛屿领地数量计算程序 (C++) 以下是使用深度优先搜索(DFS)算法解决这个问题的C++实现： ```cpp #include <vector> #include <iostream> using namespace std; 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] != 1) { return; } // 标记当前陆地已访问 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 countTerritories(vector<vector<int>>& grid) { if (grid.empty() || grid[0].empty()) { return 0; } int count = 0; int rows = grid.size(); int cols = grid[0].size(); for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { if (grid[i][j] == 1) { ++count; dfs(grid, i, j); } } } return count; } int main() { // 示例输入 vector<vector<int>> grid = { {1, 1, 0, 0, 0}, {1, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 1, 1} }; cout << "领地数量: " << countTerritories(grid) << endl; return 0; } ``` ## 代码说明： 1. `dfs`函数实现深度优先搜索，用于标记和访问所有相连的陆地 2. `countTerritories`函数遍历整个网格，每当发现未访问的陆地(值为1)时，增加计数并启动DFS 3. 主函数提供了一个示例网格并输出领地数量 ## 注意事项： 1. 输入网格会被修改，因为DFS会标记已访问的陆地。如果需要保留原始数据，应该先创建副本。 2. 对于非常大的网格，DFS可能导致栈溢出，可以考虑使用BFS或迭代式DFS。 3. 该算法的时间复杂度是O(n×m)，因为每个网格单元最多被访问一次。 ######[AI写代码神器 | 567点数解答 | 2025-03-29 10:15:29]