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

5天前比赛题解63

一、问题背景

题目模拟了扫雷游戏的场景：给定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[x][y].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[x].find(y) != mines[x].end()) {
                    for (auto& mine : mines[x][y]) {
                        if (!mine.exploded) {
                            mine.exploded = true;
                            count++;
                            q.push(mine); // 新引爆的炸雷加入队列
                        }
                    }
                }
            }
        }
    }
    
    cout << count << endl;
    return 0;
}