扫雷（蓝桥杯）

题目描述

小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下，在一个二维平面上放置着 n 个炸雷，第 i 个炸雷 (xi , yi ,ri) 表示在坐标 (xi , yi) 处存在一个炸雷，它的爆炸范围是以半径为 ri 的一个圆。

为了顺利通过这片土地，需要玩家进行排雷。玩家可以发射 m 个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭 (xj , yj ,rj) 表示这个排雷火箭将会在 (xj , yj) 处爆炸，它的爆炸范围是以半径为 rj 的一个圆，在其爆炸范围内的炸雷会被引爆。同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷？

你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。

输入格式

输入的第一行包含两个整数 n、m.

接下来的 n 行，每行三个整数 xi , yi ,ri，表示一个炸雷的信息。

再接下来的 m 行，每行三个整数 xj , yj ,rj，表示一个排雷火箭的信息。

输出一个整数表示答案。

样例输入

样例输出

提示

示例图如下，排雷火箭 1 覆盖了炸雷 1，所以炸雷 1 被排除；炸雷 1 又覆盖了炸雷 2，所以炸雷 2 也被排除。

蓝桥杯2022年第十三届省赛真题扫雷

对于 40% 的评测用例：0 ≤ x, y ≤ 109 , 0 ≤ n, m ≤ 103 , 1 ≤ r ≤ 10.

对于 100% 的评测用例：0 ≤ x, y ≤ 109 , 0 ≤ n, m ≤ 5 × 104 , 1 ≤ r ≤ 10.

第一种

图的深度优先遍历，邻接表实现，由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，明显会超时。(WA)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define int long long
using namespace std;
const int N=5e3+10;
bool st[N];
int n,m;
//存炸弹
struct node
{int x,y,r;
}stu[N];
vector<int>v[N];
//判断是否在这颗雷是否在这个圆
bool sqr(int x,int y,int xx,int yy,int r)
{if((xx-x)*(xx-x)+(yy-y)*(yy-y)<=r*r) return true;return false;
}
//连成一个连通图 雷在这个雷的范围内的就扩展
void add(int idx)
{int x=stu[idx].x,y=stu[idx].y,r=stu[idx].r;for(int i=1;i<=n;i++){if(i!=idx){if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i);}}
}
//看有多少颗符合要求的炸弹
int dfs(int idx)
{int sum=1;st[idx]=1;for(int i=0;i<v[idx].size();i++){int j=v[idx][i];if(!st[j]){st[j]=1;sum+=dfs(j);}}return sum;
}
//计算这颗排雷火箭能炸多少地雷
int dfs_Trave(int x,int y,int r)
{int sum=0;for(int i=1;i<=n;i++){if(sqr(stu[i].x,stu[i].y,x,y,r)){if(!st[i])sum+=dfs(i);}}return sum;
}
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){int x,y,r;cin>>x>>y>>r;stu[i]={x,y,r};}for(int i=1;i<=n;i++){add(i);}int sum=0;for(int i=1;i<=m;i++){int x,y,r;cin>>x>>y>>r;sum+=dfs_Trave(x,y,r);}cout<<sum<<endl;return 0;
}

图的深度优先遍历，邻接表实现
由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，
先把坐标按x轴从小到大排序，再按y轴从小到大排序
当许多坐标扎堆在同一点的时候，应当去掉重复的点，只留下半径最大的点。
不然建图的时候有O(n^2)的时间复杂度。
AC版

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N=5e4+10;
bool st[N];
map<PII,int>mp;
int n,m,n1=0;
//存炸弹
struct node
{int x,y,r,cnt;bool operator < (node const & a) const{if(x!=a.x)return x<a.x;return y<a.y;}
}stu[N];
/*
bool cmp(node xx,node yy)
{if(xx.x==yy.x) return xx.y<yy.y;return xx.x<yy.x;
}*/
vector<int>v[N];
//判断是否在这颗雷是否在这个圆
bool sqr(int x,int y,int xx,int yy,int r)
{if((xx-x)*(xx-x)+(yy-y)*(yy-y)<=r*r) return true;return false;
}
//连成一个连通图 雷在这个雷的范围内的就扩展
void add(int idx)
{int x=stu[idx].x,y=stu[idx].y,r=stu[idx].r;for(int i=idx-1;i>=0;i--){if(r<(x-stu[i].x)) break;if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i);}for(int i=idx+1;i<=n1;i++){if(r<(stu[i].x-x)) break;if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i);}
}
//看有多少颗符合要求的炸弹
int dfs(int idx)
{int sum=stu[idx].cnt;st[idx]=1;for(int i=0;i<v[idx].size();i++){int j=v[idx][i];if(!st[j]){st[j]=1;sum+=dfs(j);}}return sum;
}
//计算这颗排雷火箭能炸多少地雷
int dfs_Trave(int x,int y,int r)
{node e1={x-r,y,r,1},e2={x+r,y,r,1};int l1=lower_bound(stu+1,stu+1+n1,e1)-stu;int r1=upper_bound(stu+1,stu+1+n1,e2)-stu;int sum=0;for(int i=l1;i<=r1;i++){if(sqr(stu[i].x,stu[i].y,x,y,r)){if(!st[i])sum+=dfs(i);}}return sum;
}
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){int x,y,r;cin>>x>>y>>r;int id=mp[{x,y}];if(id!=0){stu[id].r=max(stu[id].r,r);stu[id].cnt++;}else{int xx=1;n1++;stu[n1].x=x;stu[n1].y=y;stu[n1].r=r;stu[n1].cnt=1;mp[{x,y}]=n1;}}sort(stu+1,stu+1+n1);for(int i=1;i<=n1;i++){add(i);}int sum=0;for(int i=1;i<=m;i++){int x,y,r;cin>>x>>y>>r;sum+=dfs_Trave(x,y,r);}cout<<sum<<endl;return 0;
}

第二种

图的广度优先遍历，邻接表实现
由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，
先把坐标按x轴从小到大排序，再按y轴从小到大排序
当许多坐标扎堆在同一点的时候，应当去掉重复的点，只留下半径最大的点。
不然建图的时候有O(n^2)的时间复杂度。

AC版

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#include<vector>
#include<set>
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N=5e4+10;
map<PII,int>mp;
bool st[N];
vector<int>v[N];
int n,m,n1;
struct node
{int x,y,r,num;bool operator < (node const &a) const{if(x!=a.x) return x<a.x;return y<a.y;}
}stu[N];
bool sqr(int x1,int y1,int x2,int y2,int r)
{if((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)<=r*r) return true;return false;
}
void add(int idx)
{int x=stu[idx].x,y=stu[idx].y,r=stu[idx].r;for(int i=idx-1;i>=0;i--){if(r<(x-stu[i].x)) break;if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i);}for(int i=idx+1;i<=n1;i++){if(r<(stu[i].x-x)) break;if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i);}
}
int bfs(int idx)
{int sum=stu[idx].num;queue<int>q;q.push(idx);st[idx]=1;while(q.size()){int t=q.front();q.pop();for(int i=0;i<v[t].size();i++){int j=v[t][i];if(!st[j]){st[j]=1;sum+=bfs(j);}}}return sum;
}
int bfs_Trave(int x,int y,int r)
{node e1={x-r,y,r,1},e2={x+r,y,r,1};int l1=lower_bound(stu+1,stu+1+n1,e1)-stu;int r1=upper_bound(stu+1,stu+1+n1,e2)-stu;int sum=0;for(int i=l1;i<=r1;i++){if(sqr(stu[i].x,stu[i].y,x,y,r)){if(!st[i])sum+=bfs(i);}}return sum;
}
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){int x,y,r;cin>>x>>y>>r;int xx=mp[{x,y}];if(xx!=0){stu[xx].r=max(stu[xx].r,r);stu[xx].num++;}else{n1++;stu[n1]={x,y,r,1};mp[{x,y}]=n1;}}   sort(stu+1,stu+1+n1);for(int i=1;i<=n1;i++){add(i);}int sum=0;for(int i=0;i<m;i++){int x,y,r;cin>>x>>y>>r;sum+=bfs_Trave(x,y,r);}cout<<sum<<endl;return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/296791.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！