题目描述
acwing过7个,蓝桥官网可ac。
样例
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n,m;
map<pair<int,int>,pair<int,int>> mp; //{{x,y},{r,cnt}}
int res;
void dfs(int x,int y,int r)
{
//雷的半径很小,可以枚举以雷为中心的r*r个小方格,爆炸范围就在其中
for(int a=x-r;a<=x+r;a++)
{
for(int b = y-r; b <= y + r; b++)
{
if(a<0 || b<0 || a>1e9 || b>1e9) continue;
if((x-a)*(x-a) + (y-b)*(y-b) > r*r) continue; //除去冗余方格,这些小方格不会被爆炸波及
pair<int,int> t = {a,b};
if(mp.count(t) == 0) continue; //小方格t无雷,再检查下一个小方格
else
{
int r1 = mp[t].first, cnt = mp[t].second;
mp.erase(mp.find(t)); //t有雷,雷被引爆,去除并以当前雷dfs
res += cnt;
dfs(a,b,r1);
}
}
}
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x,y,r;cin>>x>>y>>r;
if(mp.count({x,y}) == 0) //该坐标第一次出现
{
mp[{x,y}] = {r,1};
}
else //多个雷的坐标相同,取最大的那个
{
mp[{x,y}].first = max(mp[{x,y}].first, r);
mp[{x,y}].second ++; //雷的cnt加一
}
}
for(int i=1;i<=m;i++)
{
int x,y,r;cin>>x>>y>>r;
dfs(x,y,r);
}
cout<<res<<'\n';
return 0;
}