天梯赛L2寻宝图（BFS）保姆级教程：从连通块判断到有宝藏岛屿统计，一次讲透

天梯赛L2寻宝图BFS从连通块到宝藏岛屿的完全解析当面对迷宫类图论问题时很多选手会被连通块判断和特殊条件处理绊住脚步。这道寻宝图问题正是考察BFS/DFS算法应用的经典题型需要处理地图遍历、连通块统计以及带条件的岛屿判断。我们将从算法原理到代码实现完整拆解这道题的解决思路。1. 问题重述与核心难点题目给定一个N×M的网格地图每个格子可能是0水域1普通陆地2-9藏有宝藏的陆地岛屿定义被水域完全包围的连通陆地区域。需要统计地图中岛屿的总数量含有宝藏的岛屿数量只要岛屿中存在至少一个宝藏格子即算数据范围1 N×M ≤ 10^5这意味着我们必须使用时间复杂度为O(NM)的算法。常见误区未正确处理地图边界默认外围是水域连通块计数时重复访问宝藏判断不完整只检查起点而忽略连通块内其他点2. BFS算法框架搭建广度优先搜索(BFS)是解决此类网格连通问题的标准方法。基本框架如下// 方向数组上、下、左、右 int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; void bfs(int x, int y) { queuepairint,int q; q.push({x,y}); visited[x][y] true; while(!q.empty()) { auto [cx,cy] q.front(); q.pop(); for(auto [dx,dy] : dirs) { int nx cx dx, ny cy dy; if(nx0 nxn ny0 nym !visited[nx][ny] grid[nx][ny]!0) { visited[nx][ny] true; q.push({nx,ny}); } } } }3. 连通块与宝藏判断的实现技巧我们需要在BFS过程中同时完成两项任务标记连通区域岛屿检查该岛屿是否含有宝藏改进后的BFS函数应返回布尔值表示当前岛屿是否含有宝藏bool bfs(int x, int y) { bool hasTreasure (grid[x][y] 1); queuepairint,int q; q.push({x,y}); visited[x][y] true; while(!q.empty()) { auto [cx,cy] q.front(); q.pop(); for(auto [dx,dy] : dirs) { int nx cx dx, ny cy dy; if(nx0 nxn ny0 nym !visited[nx][ny] grid[nx][ny]!0) { if(grid[nx][ny] 1) hasTreasure true; visited[nx][ny] true; q.push({nx,ny}); } } } return hasTreasure; }4. 完整解题流程与边界处理主函数需要遍历整个网格对每个未访问的陆地格子启动BFSint totalIslands 0, treasureIslands 0; for(int i0; in; i) { for(int j0; jm; j) { if(!visited[i][j] grid[i][j] ! 0) { totalIslands; if(bfs(i,j)) treasureIslands; } } } cout totalIslands treasureIslands endl;关键细节访问数组visited需要初始化为false输入数据可能包含换行符需正确处理网格存储建议使用vectorstring而非二维数组便于处理大尺寸数据5. 性能优化与易错点内存优化当N×M接近10^5时避免使用静态数组改用动态容器布尔访问数组可用vectorbool专有化实现节省空间常见错误排查方向数组遗漏少写某个方向导致连通块判断不全边界条件错误忘记检查网格边界导致越界访问初始状态设置未正确初始化访问数组字符数字比较直接比较数字而非ASCII字符如grid[x][y] 1应为grid[x][y] 1测试用例验证建议测试以下边界情况全水域地图应输出0 0单格陆地无宝藏单格陆地有宝藏多个相连宝藏格组成的岛屿最大尺寸网格验证时间效率6. 算法扩展与变式思考掌握基础解法后可以思考以下变式问题三维寻宝图将网格扩展为立方体连通条件增加上下方向动态寻宝图宝藏位置随时间变化需要处理时间维度最短寻宝路径从起点到宝藏格的最短路径问题多源点BFS同时从多个陆地格开始扩散这些变式在各类编程竞赛中都有可能出现理解基础BFS应用是解决它们的关键。7. 实战代码展示以下是经过优化的完整AC代码包含详细注释#include iostream #include vector #include queue using namespace std; const int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; int main() { ios::sync_with_stdio(false); // 加速输入输出 cin.tie(nullptr); int n, m; cin n m; vectorstring grid(n); for(auto row : grid) cin row; vectorvectorbool visited(n, vectorbool(m, false)); int total 0, treasure 0; for(int i0; in; i) { for(int j0; jm; j) { if(!visited[i][j] grid[i][j] ! 0) { // 新岛屿发现 total; bool hasTreasure false; queuepairint,int q; q.push({i,j}); visited[i][j] true; // 检查起点是否为宝藏 if(grid[i][j] 1) hasTreasure true; // BFS遍历整个岛屿 while(!q.empty()) { auto [x,y] q.front(); q.pop(); for(auto [dx,dy] : dirs) { int nx x dx, ny y dy; if(nx0 nxn ny0 nym !visited[nx][ny] grid[nx][ny]!0) { if(grid[nx][ny] 1) hasTreasure true; visited[nx][ny] true; q.push({nx,ny}); } } } if(hasTreasure) treasure; } } } cout total treasure endl; return 0; }8. 竞赛技巧与经验分享在实际比赛中处理此类题目时快速搭建框架先写出BFS/DFS的标准模板模块化思考将连通块计数和宝藏判断分离防御性编程添加边界检查断言可视化调试对于小样例手工绘制访问过程性能预估在提交前估算最坏情况下的时间复杂度遇到WAWrong Answer时检查样例中的边缘格子处理验证访问数组的初始化状态确认方向数组是否完整输出中间结果进行调试掌握这类问题的核心在于理解网格遍历的本质以及如何高效地标记和处理连通区域。通过这道题的练习可以建立起解决更复杂图论问题的信心和基础。