当前位置：首页 > news >正文

天梯赛编程题 L2—048 寻宝图题解

news 2026/5/12 2:36:50

题面如下：

【算法题解】岛屿计数与宝藏探测（BFS/DFS 连通块）

题目来源：经典图论遍历问题变体
难度：⭐⭐ (入门/普及-)
标签：BFSDFS连通块Flood Fill

📋 题目描述

给定一个N×MN \times MN×M的字符网格地图，其中包含三种类型的格子：

'0'：代表水域。
'1'：代表普通陆地。
'2'~'9'：代表埋有宝藏的陆地。

定义规则：

岛屿：由上下左右四个方向相邻的陆地（即字符'1'到'9'）组成的连通区域。
宝藏岛屿：如果一个岛屿中至少包含一个字符在'2'到'9'之间的格子，则称该岛屿为“宝藏岛屿”。

任务：
请编写程序统计地图中岛屿的总数以及含有宝藏的岛屿数量。

💡 解题思路

这是一道典型的连通块计数问题（Connected Components），可以通过广度优先搜索 (BFS)或深度优先搜索 (DFS)来解决。核心思想是“泛洪填充”（Flood Fill）。

1. 算法流程

我们可以按照以下步骤进行：

初始化：
- 读取输入地图。
- 创建一个与地图大小相同的visited数组，初始化为false，用于记录哪些格子已经被访问过。
- 初始化计数器：totalIslands = 0，treasureIslands = 0。
遍历地图：
- 使用双重循环遍历每一个格子(i,j)(i, j)(i,j)。
- 如果当前格子是陆地（grid[i][j] != '0'）且未被访问过（!visited[i][j]）：
  - 说明发现了一个新的岛屿，totalIslands加 1。
  - 设置一个布尔标记hasTreasure = false。
  - 启动BFS或DFS遍历整个连通块。
搜索过程 (以 BFS 为例)：
- 将起始点(i,j)(i, j)(i,j)加入队列，并标记为已访问。
- 当队列不为空时：
  - 取出队首元素(x,y)(x, y)(x,y)。
  - 检查宝藏：如果grid[x][y]的字符值在'2'到'9'之间，将hasTreasure设为true。
  - 扩展邻居：检查(x,y)(x, y)(x,y)的上下左右四个方向(nx,ny)(nx, ny)(nx,ny)：
    - 边界检查：0≤nx<N0 \le nx < N0≤nx<N且0≤ny<M0 \le ny < M0≤ny<M。
    - 条件检查：是陆地（!= '0'）且未访问过。
    - 如果满足，将其加入队列并标记为已访问。
统计结果：
- 当一次完整的 BFS/DFS 结束后，检查hasTreasure。
- 如果为true，则treasureIslands加 1。
输出：打印两个统计数值。

2. 数学表达

设地图为矩阵GGG，大小为N×MN \times MN×M。
定义连通关系：若格子AAA和BBB相邻（上下左右）且均为陆地，则A∼BA \sim BA∼B。
岛屿即为等价类[p]={q∣p∼∗q}[p] = \{ q \mid p \sim^* q \}[p]={q∣p∼∗q}，其中∼∗\sim^*∼∗表示连通关系的传递闭包。

我们需要计算：
Total=∣{[p]∣G[p]≠′0′}∣ \text{Total} = |\{ [p] \mid G[p] \neq '0' \}|Total=∣{[p]∣G[p]=′0′}∣
Treasure=∣{[p]∣∃q∈[p],′2′≤G[q]≤′9′}∣ \text{Treasure} = |\{ [p] \mid \exists q \in [p], '2' \le G[q] \le '9' \}|Treasure=∣{[p]∣∃q∈[p],′2′≤G[q]≤′9′}∣

💻 代码实现 (C++ BFS)

这里提供一份标准的 C++ 实现，修复了常见的语法错误（如变量名不一致、符号错误等）。为了兼容旧编译器，未使用 C++17 的结构化绑定。

#include<bits/stdc++.h>usingnamespacestd;intmain(){// 优化 I/O 操作，加快读取速度ios::sync_with_stdio(false);cin.tie(nullptr);intN,M;if(!(cin>>N>>M))return0;vector<string>grid(N);for(inti=0;i<N;++i){cin>>grid[i];}// visited 数组：记录每个格子是否被访问过vector<vector<bool>>visited(N,vector<bool>(M,false));inttotalIslands=0;inttreasureIslands=0;// 方向数组：上、下、左、右intdx[]={-1,1,0,0};intdy[]={0,0,-1,1};for(inti=0;i<N;++i){for(intj=0;j<M;++j){// 如果是陆地且未访问，说明发现新岛屿if(grid[i][j]!='0'&&!visited[i][j]){totalIslands++;boolhasTreasure=false;// 定义 BFS 队列queue<pair<int,int>>q;q.push({i,j});visited[i][j]=true;// 入队时立即标记，防止重复入队while(!q.empty()){// 获取队首元素pair<int,int>cur=q.front();q.pop();intx=cur.first;inty=cur.second;// 检查当前点是否有宝藏 ('2' ~ '9')if(grid[x][y]>='2'&&grid[x][y]<='9'){hasTreasure=true;}// 遍历四个方向for(intd=0;d<4;++d){intnx=x+dx[d];intny=y+dy[d];// 边界检查 + 是陆地 + 未访问if(nx>=0&&nx<N&&ny>=0&&ny<M&&grid[nx][ny]!='0'&&!visited[nx][ny]){visited[nx][ny]=true;q.push({nx,ny});}}}// 如果该岛屿包含宝藏，计数加一if(hasTreasure){treasureIslands++;}}}}cout<<totalIslands<<" "<<treasureIslands<<"\n";return0;}