蓝桥杯2022省赛B组扫雷问题：BFS算法实战解析

19339201706

一、问题背景

题目模拟了扫雷游戏的场景：给定n个炸雷的位置和爆炸半径，以及m个排雷火箭的位置和引爆半径。当一个炸雷被引爆后，会引爆在其爆炸范围内的其他未引爆炸雷，要求计算最终被引爆的炸雷总数。

二、核心算法思路

• BFS广度优先搜索：模拟连锁引爆过程
• 空间优化存储：使用嵌套unordered_map存储炸雷位置
• 距离优化计算：使用距离平方避免浮点运算
  
  

三、完整代码解析（带注释）

1. #include <iostream>
   
2. #include <vector>
   
3. #include <queue>
   
4. #include <cmath>
   
5. #include <unordered_map>
   
6. using namespace std;
   
7. 
   
8. // 定义炸雷/火箭结构体
   
9. struct Point {
   
10.     int x, y, r;        // 坐标和爆炸半径
    
11.     bool exploded = false; // 是否已被引爆
    
12. };
    
13. 
    
14. // 计算两点间距离平方（避免开方运算）
    
15. int distance2(int x1, int y1, int x2, int y2) {
    
16.     int dx = x1 - x2;
    
17.     int dy = y1 - y2;
    
18.     return dx*dx + dy*dy;
    
19. }
    
20. 
    
21. int main() {
    
22.     ios::sync_with_stdio(false);  // 关闭同步提升IO速度
    
23.     cin.tie(nullptr);
    
24.    
    
25.     int n, m;  // n-炸雷数量 m-火箭数量
    
26.     cin >> n >> m;
    
27.    
    
28.     // 使用双层哈希表存储炸雷（x→y→炸雷列表）
    
29.     unordered_map<int, unordered_map<int, vector<Point>>> mines;
    
30.     vector<Point> mine_list;  // 炸雷列表备份
    
31.    
    
32.     // 读取炸雷数据
    
33.     for (int i = 0; i < n; ++i) {
    
34.         int x, y, r;
    
35.         cin >> x >> y >> r;
    
36.         mine_list.push_back({x, y, r, false});
    
37.         mines[x][y].push_back({x, y, r, false});
    
38.     }
    
39.    
    
40.     queue<Point> q;  // BFS队列
    
41.     int count = 0;   // 引爆计数器
    
42.    
    
43.     // 处理排雷火箭（初始引爆点）
    
44.     for (int i = 0; i < m; ++i) {
    
45.         int x, y, r;
    
46.         cin >> x >> y >> r;
    
47.         q.push({x, y, r, false});
    
48.     }
    
49.    
    
50.     // BFS处理引爆过程
    
51.     while (!q.empty()) {
    
52.         Point current = q.front();
    
53.         q.pop();
    
54.         
    
55.         // 计算当前爆炸影响范围
    
56.         int min_x = current.x - current.r;
    
57.         int max_x = current.x + current.r;
    
58.         int min_y = current.y - current.r;
    
59.         int max_y = current.y + current.r;
    
60.         
    
61.         // 遍历范围内的所有可能位置
    
62.         for (int x = min_x; x <= max_x; ++x) {
    
63.             for (int y = min_y; y <= max_y; ++y) {
    
64.                 // 距离检查（使用平方比较优化）
    
65.                 if (distance2(current.x, current.y, x, y) > current.r * current.r)
    
66.                     continue;
    
67.                
    
68.                 // 检查该位置是否存在炸雷
    
69.                 if (mines.find(x) != mines.end() && mines[x].find(y) != mines[x].end()) {
    
70.                     for (auto& mine : mines[x][y]) {
    
71.                         if (!mine.exploded) {
    
72.                             mine.exploded = true;
    
73.                             count++;
    
74.                             q.push(mine); // 新引爆的炸雷加入队列
    
75.                         }
    
76.                     }
    
77.                 }
    
78.             }
    
79.         }
    
80.     }
    
81.    
    
82.     cout << count << endl;
    
83.     return 0;
    
84. }

复制代码

四、关键算法点详解

• BFS队列应用：使用队列管理待处理的爆炸点
• 哈希表存储优化：O(1)时间复杂度快速查找指定位置炸雷
• 爆炸范围处理：通过整数范围遍历+距离验证确保准确性
• 状态标记：exploded字段防止重复计数
  
  

五、性能优化技巧

• 使用距离平方比较避免浮点运算
• unordered_map实现快速查找
• 提前终止条件判断
  
  

来源：蓝桥杯2022省赛B组扫雷问题：BFS算法实战解析