蓝桥杯2022省赛B组扫雷问题：BFS算法实战解析
https://dajuwangluo.cn/zb_users/upload/2025/06/202506231750665249563655.jpg一、问题背景题目模拟了扫雷游戏的场景：给定n个炸雷的位置和爆炸半径，以及m个排雷火箭的位置和引爆半径。当一个炸雷被引爆后，会引爆在其爆炸范围内的其他未引爆炸雷，要求计算最终被引爆的炸雷总数。二、核心算法思路[*]BFS广度优先搜索：模拟连锁引爆过程
[*]空间优化存储：使用嵌套unordered_map存储炸雷位置
[*]距离优化计算：使用距离平方避免浮点运算
三、完整代码解析（带注释）#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_map>
using namespace std;
// 定义炸雷/火箭结构体
struct Point {
int x, y, r; // 坐标和爆炸半径
bool exploded = false; // 是否已被引爆
};
// 计算两点间距离平方（避免开方运算）
int distance2(int x1, int y1, int x2, int y2) {
int dx = x1 - x2;
int dy = y1 - y2;
return dx*dx + dy*dy;
}
int main() {
ios::sync_with_stdio(false);// 关闭同步提升IO速度
cin.tie(nullptr);
int n, m;// n-炸雷数量 m-火箭数量
cin >> n >> m;
// 使用双层哈希表存储炸雷（x→y→炸雷列表）
unordered_map<int, unordered_map<int, vector<Point>>> mines;
vector<Point> mine_list;// 炸雷列表备份
// 读取炸雷数据
for (int i = 0; i < n; ++i) {
int x, y, r;
cin >> x >> y >> r;
mine_list.push_back({x, y, r, false});
mines.push_back({x, y, r, false});
}
queue<Point> q;// BFS队列
int count = 0; // 引爆计数器
// 处理排雷火箭（初始引爆点）
for (int i = 0; i < m; ++i) {
int x, y, r;
cin >> x >> y >> r;
q.push({x, y, r, false});
}
// BFS处理引爆过程
while (!q.empty()) {
Point current = q.front();
q.pop();
// 计算当前爆炸影响范围
int min_x = current.x - current.r;
int max_x = current.x + current.r;
int min_y = current.y - current.r;
int max_y = current.y + current.r;
// 遍历范围内的所有可能位置
for (int x = min_x; x <= max_x; ++x) {
for (int y = min_y; y <= max_y; ++y) {
// 距离检查（使用平方比较优化）
if (distance2(current.x, current.y, x, y) > current.r * current.r)
continue;
// 检查该位置是否存在炸雷
if (mines.find(x) != mines.end() && mines.find(y) != mines.end()) {
for (auto& mine : mines) {
if (!mine.exploded) {
mine.exploded = true;
count++;
q.push(mine); // 新引爆的炸雷加入队列
}
}
}
}
}
}
cout << count << endl;
return 0;
}
四、关键算法点详解
[*]BFS队列应用：使用队列管理待处理的爆炸点
[*]哈希表存储优化：O(1)时间复杂度快速查找指定位置炸雷
[*]爆炸范围处理：通过整数范围遍历+距离验证确保准确性
[*]状态标记：exploded字段防止重复计数
五、性能优化技巧
[*]使用距离平方比较避免浮点运算
[*]unordered_map实现快速查找
[*]提前终止条件判断
来源：蓝桥杯2022省赛B组扫雷问题：BFS算法实战解析
页:
[1]