2022年蓝桥杯省赛B组扫雷（洛谷P8785）解题全解析：代码+思路+步骤详解

一、题目解读

2022年蓝桥杯省赛B组机器人塔（洛谷P8785）是一道经典的算法题目，要求处理在一个二维平面上布置的炸雷与排雷火箭。炸雷具有爆炸半径，当排雷火箭引爆后，会触发周围范围内未被引爆的炸雷，形成连锁反应。题目需要计算最终引爆的炸雷数量，考验对广度优先搜索（BFS）与距离计算的灵活运用，以及对多炸雷位置叠加处理的能力。

二、解题思路

核心思路采用BFS遍历排雷火箭，通过计算爆炸范围动态引爆周围炸雷。具体步骤为：

1. 使用unordered_map存储每个位置的炸雷列表，允许同一坐标存在多个炸雷；

2. 通过BFS依次处理排雷火箭，计算其爆炸范围内的所有炸雷坐标；

3. 若炸雷未被引爆，则标记并加入队列，形成连锁引爆；

4. 统计引爆次数，最终输出结果。

三、解题步骤

1. 数据读取：输入炸雷数量n与排雷火箭数量m，存储炸雷坐标(x, y, r)及排雷火箭位置；

2. 初始化结构：建立mines哈希表记录炸雷分布，q队列存储待引爆的火箭/炸雷；

3. BFS引爆处理：

    取出队列头部元素，计算爆炸范围矩形区域；

    遍历区域内所有坐标，判断炸雷是否存在且未引爆；

    若符合条件，标记炸雷引爆并加入队列，继续触发后续引爆；

4. 统计引爆数量：通过队列循环次数或标记变量计算最终结果。

四、代码及注释

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_map>
using namespace std;

struct Point {
    int x, y, r;   // 坐标(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);
    cin.tie(nullptr);   // 加速输入输出

    int n, m;
    cin >> n >> m;   // 读取炸雷与排雷火箭数量

    // 使用map存储每个位置的炸雷列表，相同位置可能有多个炸雷
    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;   // 引爆队列
    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;
}

五、总结

该解法巧妙利用unordered_map处理位置重叠的炸雷，结合BFS实现高效引爆传播。关键点在于：

1. 爆炸范围计算采用距离平方避免耗时开方；

2. 通过队列实现递归式引爆，避免手动递归栈溢出风险；

3. 标记引爆状态避免重复计算。

在实际算法设计中，需注意数据结构的选择与边界条件的严谨处理，以提升效率与准确性。