扫雷 【搜索，哈希】

9.扫雷 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+100;
int n,m,res=0;
struct pt{int x,y,r;
};
typedef pair<int,int> pii;
map <pii,int> a;//炸雷的map,键是x,y,值是r
map <pii,int> b;//排雷火箭的map,键是x,y,值是r
map <pii,int> cnt;//炸雷数量的map,键是x,y,值是炸雷数量cnt
queue <pt> q;void bfs()
{while(!q.empty()){auto t=q.front();q.pop();int tx=t.x,ty=t.y,tr=t.r;for(int i=tx-tr;i<=tx+tr;i++){for(int j=ty-tr;j<=ty+tr;j++){int dx=tx-i;int dy=ty-j;if(dx*dx+dy*dy>tr*tr||cnt[{i,j}]==0)//范围外的或者数量为0的continue;res+=cnt[{i,j}];//该坐标雷的数量cnt.erase({i,j});//被引爆了的删掉该坐标q.push((pt){i,j,a[{i,j}]});//被引爆的雷入队}}}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n>>m;for(int i=1;i<=n;i++){int x,y,r;cin>>x>>y>>r;a[{x,y}]=max(a[{x,y}],r);//相同坐标记录半径大的cnt[{x,y}]++;}for(int i=1;i<=m;i++){int x,y,r;cin>>x>>y>>r;b[{x,y}]=max(b[{x,y}],r);//相同坐标记录半径大的}for(auto i:b)//排雷火箭都入队{q.push((pt){i.first.first,i.first.second,i.second});}bfs();cout<<res;return 0;
}