PTA题库‘寻宝图’题解：用DFS搞定连通块与特殊值统计（C++实现）-洪萨配资

PTA题库‘寻宝图’题解：深度优先搜索实战与优化全解析

第一次遇到PTA题库中的"寻宝图"问题时，很多同学会被网格搜索和连通块统计的需求难住。这道题看似简单，却涵盖了DFS算法、边界处理、状态标记等多个核心编程概念。本文将带大家从零开始拆解问题，不仅给出可提交的C++代码，更会深入讲解如何避免常见错误、优化算法效率，以及如何将这类解题思路迁移到其他相似题目中。

1. 问题重述与核心思路

题目给定一个由数字0-9组成的n×m网格，要求统计其中所有非零数字组成的连通区域数量（称为"宝藏区"），并特别统计其中包含数字大于1的连通区域数量。连通的定义是上下左右相邻。

关键解题步骤分解：

网格遍历：逐个检查每个网格点
连通区域判断：当遇到未被访问的非零点时，启动DFS/BFS
特殊值检测：在搜索过程中检查是否存在值>1的点
结果统计：维护两个计数器分别记录总区域数和含特殊值的区域数

注意：题目中的"连通"仅考虑上下左右四个方向，不考虑对角线方向，这点在编写方向数组时需特别注意。

2. DFS实现详解与代码逐行解析

让我们先看完整的C++实现，然后逐步拆解关键部分：

#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; // 根据题目约束调整 vector<vector<int>> grid; vector<vector<bool>> visited; int specialRegions = 0, totalRegions = 0; int n, m; // 方向数组：上、右、下、左 const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, 1, 0, -1}; void dfs(int x, int y, bool& hasSpecial) { visited[x][y] = true; if (grid[x][y] > 1) hasSpecial = true; for (int i = 0; i < 4; ++i) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && grid[nx][ny] != 0) { if (grid[nx][ny] > 1) hasSpecial = true; dfs(nx, ny, hasSpecial); } } } int main() { cin >> n >> m; grid.assign(n, vector<int>(m)); visited.assign(n, vector<bool>(m, false)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { char c; cin >> c; grid[i][j] = c - '0'; } } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (!visited[i][j] && grid[i][j] != 0) { bool hasSpecial = false; totalRegions++; dfs(i, j, hasSpecial); if (hasSpecial) specialRegions++; } } } cout << totalRegions << " " << specialRegions << endl; return 0; }

关键代码段解析：

方向数组：
```
const int dx[] = {-1, 0, 1, 0}; // 行变化 const int dy[] = {0, 1, 0, -1}; // 列变化
```
这种定义方式比单独写四个if更简洁高效，也便于后续扩展为八方向搜索。

DFS核心逻辑：

void dfs(int x, int y, bool& hasSpecial) { visited[x][y] = true; if (grid[x][y] > 1) hasSpecial = true; for (int i = 0; i < 4; ++i) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && grid[nx][ny] != 0) { dfs(nx, ny, hasSpecial); } } }

注意边界检查(nx, ny)和访问标记的判断顺序，这是避免数组越界的关键。

主循环中的统计逻辑：

if (!visited[i][j] && grid[i][j] != 0) { bool hasSpecial = false; totalRegions++; dfs(i, j, hasSpecial); if (hasSpecial) specialRegions++; }

每次发现新的连通区域时，先增加总区域数，在DFS过程中检测是否有特殊值。

3. 常见错误与调试技巧

在实现DFS算法时，初学者常会遇到以下几类问题：

边界条件处理不当：

忘记检查数组越界，导致运行时错误
错误地将边界条件写成nx > 0而不是nx >= 0
行列索引混淆（特别是在行列从0开始还是1开始不统一时）

访问标记问题：

忘记标记已访问状态，导致无限递归
错误地在DFS返回前清除访问标记（适用于回溯问题，但不适用于连通区域统计）
使用单独的标记数组而不是修改原数组值（后者可以节省空间）

递归深度问题：

当网格很大时（如1000×1000），递归实现可能导致栈溢出
没有及时剪枝，处理包含大量连通点的区域时效率低下

输入处理陷阱：

题目输入可能使用字符而非数字直接表示网格值
行尾可能有空白字符需要处理
网格行列顺序与常规数学坐标系不一致

调试建议：对于DFS问题，可以在递归调用前打印当前位置和状态，或者使用条件断点来跟踪特定位置的搜索过程。

4. 算法优化与性能对比

原始DFS实现已经能够解决问题，但我们还可以从多个角度进行优化：

空间优化方案

优化方法	实现方式	节省空间	代码复杂度
原地标记	使用grid值0表示已访问	省去visited数组	需保留原始零值信息
位压缩	用bitset代替bool数组	减少8倍内存	访问稍复杂
分块处理	只加载部分网格到内存	适合超大网格	增加I/O复杂度

时间优化策略

迭代式DFS：

stack<pair<int, int>> s; s.push({x, y}); visited[x][y] = true; while (!s.empty()) { auto [cx, cy] = s.top(); s.pop(); if (grid[cx][cy] > 1) hasSpecial = true; for (int i = 0; i < 4; ++i) { int nx = cx + dx[i], ny = cy + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && grid[nx][ny] != 0) { visited[nx][ny] = true; s.push({nx, ny}); } } }

使用显式栈替代递归，避免栈溢出风险。