pta寻宝图c++

### PTA 寻宝图 C++ 解题思路与示例代码 #### 问题分析 该问题是关于在一个二维网格地图上统计岛屿总数以及含有宝藏的岛屿数量。输入是一个由字符组成的矩阵，其中 `0` 表示水域，`1` 或其他特定数值表示陆地或宝藏位置。通过深度优先搜索（DFS）算法可以有效地解决问题。 以下是详细的解题思路和实现代码： --- #### 解题思路 为了计算岛屿总数和含宝藏的岛屿数量，可以通过以下方式完成： - 使用 DFS 遍历整个地图中的每个格子。 - 如果当前格子是未访问过的陆地，则启动一次新的 DFS 过程，并将其标记为已访问。 - 在 DFS 的过程中，记录是否有任何宝藏存在于当前岛屿中。 - 统计每次 DFS 启动后的结果，更新岛屿总数和含宝藏的岛屿数量。 具体步骤如下： 1. 初始化变量用于存储岛屿总数和含宝藏的岛屿数量。 2. 创建一个布尔型二维数组 `visited` 来跟踪哪些格子已被访问过。 3. 对于地图中的每个格子，如果它是未被访问过的陆地，则调用 DFS 函数处理它。 4. 在 DFS 中，递归访问相邻的四个方向（上下左右），并判断是否存在宝藏。 5. 最终输出两个统计数据：岛屿总数和含宝藏的岛屿数量。 --- #### 示例代码 下面是基于上述思路编写的完整 C++ 实现代码： ```cpp #include <bits/stdc++.h> using namespace std; // 定义地图大小的最大值 const int MAX_N = 105; int n, m; // 地图行列数 char grid[MAX_N][MAX_N]; // 存储地图数据 bool visited[MAX_N][MAX_N]; // 访问状态表 // 方向数组，定义上下左右移动 int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; // 判断坐标是否合法 bool isValid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m && !visited[x][y]; } // 深度优先搜索函数 void dfs(int x, int y, bool& hasTreasure) { visited[x][y] = true; // 标记当前位置为已访问 if (grid[x][y] >= '2' && grid[x][y] <= '9') { hasTreasure = true; // 发现有宝藏 } // 遍历四个方向 for (int i = 0; i < 4; ++i) { int nx = x + dx[i], ny = y + dy[i]; if (isValid(nx, ny) && grid[nx][ny] != '0') { dfs(nx, ny, hasTreasure); } } } int main() { cin >> n >> m; // 输入地图尺寸 // 输入地图数据 for (int i = 0; i < n; ++i) { cin >> grid[i]; } memset(visited, false, sizeof(visited)); // 初始化访问状态表 int islandCount = 0, treasureIslandCount = 0; // 遍历地图中的每个格子 for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (!visited[i][j] && grid[i][j] != '0') { bool hasTreasure = false; // 当前岛屿是否有宝藏标志 dfs(i, j, hasTreasure); // 开始 DFS islandCount++; // 岛屿总数加一 if (hasTreasure) { treasureIslandCount++; // 若有宝藏，增加含宝藏岛屿计数 } } } } cout << islandCount << " " << treasureIslandCount << endl; // 输出结果 return 0; } ``` --- #### 关键点说明 1. **合法性检查** 在 DFS 调用之前，需验证目标格子是否超出边界范围或者已经被访问过[^2]。 2. **宝藏判定条件** 只有当某个格子内的字符位于 `'2'` 至 `'9'` 之间时才认为其包含宝藏[^3]。 3. **效率优化** 使用全局变量保存地图信息和访问状态能够减少内存分配开销，提高程序运行速度。 ---