2113_扫雷 蓝桥杯

code

(x, y, r) 存一颗雷或者火箭信息， 读入一个火箭，先找(x-r, x+r), (y-r, y+r)方形区域内的雷。再确定哪些落在圆内。圆内的雷按同样的方式先方形再圆形找被引爆的雷，直到没有雷可以引爆。

数据较大，5*10^4, 需要优化到O(nlogn)左右。可以给横坐标x,纵坐标y排序，查找时用二分查找。并且 0 <= x, y <= 10^9, 下标要做压缩。

cpp

map>> mp, 按>> 存雷。 mp[x][y][r]：(x, y) 点爆炸半径为 r 有几颗雷。

• res 存结果，可以引爆几颗
• 读入扫雷火箭 x, y, r。放入队列q中。
• 每次在队列取出第一个(x, y, r), 找可以被引爆的其他雷
• 找在(x-r, x+r), (y-r,y+r) 方形区域内的雷，剪枝操作。
  • xiter = mp.lower_bound(x - r), 二分查找 第一个不小于 x-r 的横坐标
  • xed = mp.upper_bound(x + r), 二分查找 第一个大于 x+r 的横坐标
  • 横坐标范围: [xiter->first, xed->first)
• 横坐标确定后找满足条件的纵坐标
  • yiter = xiter->second.lower_bound(y - r)
  • yed = xiter->second.upper_bound(y + r)
  • xiter->second 也就是 mp[x]
  • 纵坐标范围: [yiter->first, yed->first)
• 判断炸弹(xiter->first, yiter->first)是否在引爆范围，如果在：
  • yiter->second也就是mp[x][y], 得到key为半径r, value为炸弹个数的unordered_map
  • 遍历以该点为圆心的炸弹for(const auto& bm:yiter->second)
  • res += bm->second也就是当前雷的个数，
  • 将雷(xiter->first, yiter->first, bm->first)放入队列
  • 删除该点的雷：
    • 先清空纵坐标, map[x].erase(y)，yiter = xiter->second.erase(yiter)。
    • 如果mp[x]全处理完后也为空，mp.erase(x), xiter = mp.erase(xiter);
• 重复此过程，直到队列为空。 读入下一个扫雷火箭，直到所有火箭处理完。

#include 
using namespace std;

const int fff = []() {
   ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); return 0; }();

bool is_in_scope(long long x1, long long y1, long long r, long long x2, long long y2) {
   
    return (x1 - x2) * (x1 - x2) <= r * r - (y1 - y2) * (y1 - y2);
}

int main() {
   
    int n, m;
    cin >> n >> m;
    map<int, map<int, unordered_map<int, int>>> mp;
    for (int i = 0; i < n; i++) {
   
        int x, y, r;
        cin >> x >> y >> r;
        mp[x][y][r]++;
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21