题目描述
小明最近迷上了一款名为《扫雷》的游戏。
其中有一个关卡的任务如下:
在一个二维平面上放置着 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,表示一个排雷火箭的信息。
输出格式
输出一个整数表示答案。
数据范围
对于 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。
输入样例:
2 1
2 2 4
4 4 2
0 0 5
输出样例:
2
算法1 普通bfs
(暴力枚举) $O(n^2)$
时间复杂度
C++ 代码
#include<iostream>
#include<cstring>
#define x first
#define y second
using namespace std;
const int N=1=10100;
typedef pair<int,int> PII;
typedef long long ll;
int st[N][N],radis[N][N];
int g[N][N];
int m,n,res;
PII q[50001];
void bfs(int x0,int y0)
{
int hh=0,tt=0;
st[x0][y0]=true;
q[0]={x0,y0};
res++;
while(hh<=tt){
auto t=q[hh++];
int xi=t.x,yi=t.y;
int ri=radis[xi][yi];
for(int x=xi-ri;x<=xi+ri;x++)
for(int y=yi-ri;y<=yi+ri;y++)
if(((x-xi)*(x-xi)+(y-yi)*(y-yi))<=ri*ri){
if(x<0||y<0) continue;
if(st[x][y]||!g[x][y]) continue;
st[x][y]=true;
q[++tt]={x,y};
res++;
}
}
}
int main(){
cin>>n>>m;
for(int i = 1; i <= n; i++) {
int x, y, r;
cin >> x >> y >> r;
g[x][y]=1;
radis[x][y]=r;
}
for(int i=1;i<=m;i++){
int xi,yi,ri;
cin>>xi>>yi>>ri;
for(int x=xi-ri;x<=xi+ri;x++)
for(int y=yi-ri;y<=yi+ri;y++)
if(((x-xi)*(x-xi)+(y-yi)*(y-yi))<=ri*ri){
if(!g[x][y]) continue;
if(st[x][y]) continue;
bfs(x,y);
}
}
cout<<res<<endl;
return 0;
}
N开的大会爆内存
*N开到1010 只能过4个数据*
----------
正确做法借助哈希表优化空间
算法2
(哈希表+dfs)
时间复杂度(mrr+nrr)
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=50010,M=9999997;
typedef long long ll;
int st[M],id[M];
ll h[M];
struct Circle{
int x,y,r;
}circle[N];
int n,m;
//hash表
ll get_key(int x,int y){
return x*(ll)(1e9+11)+y;
}
int find(int x,int y){
int t=(get_key(x,y)%M+M)%M;
while(h[t]!=-1&&h[t]!=get_key(x,y))
{
t++;
if(t==M) t=0;
}
return t;
}
void dfs(int xi,int yi,int ri)
{
int i=find(xi,yi);
st[i]=true;
for(int x=xi-ri;x<=xi+ri;x++)
for(int y=yi-ri;y<=yi+ri;y++)
if(((x-xi)*(x-xi)+(y-yi)*(y-yi))<=ri*ri){
int t=find(x,y);
if(st[t]||!id[t]) continue;
dfs(x,y,circle[id[t]].r);
}
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++) {
cin>>circle[i].x>>circle[i].y>>circle[i].r;
int t=find(circle[i].x,circle[i].y);
if(h[t]==-1) h[t]=get_key(circle[i].x,circle[i].y);
if(!id[t]||circle[id[t]].r<circle[i].r) id[t]=i;
}
for(int i=0;i<m;i++){
int xi,yi,ri;
cin>>xi>>yi>>ri;
for(int x=xi-ri;x<=xi+ri;x++)
for(int y=yi-ri;y<=yi+ri;y++)
if(((x-xi)*(x-xi)+(y-yi)*(y-yi))<=ri*ri){
int t=find(x,y);
if(st[t]||!id[t]) continue;
dfs(x,y,circle[id[t]].r);
}
}
int res=0;
for(int i=1;i<=n;i++){
if(st[find(circle[i].x,circle[i].y)]) res++;
}
cout<<res<<endl;
return 0;
}
算法2
(哈希表+dfs)
时间复杂度(mrr+nrr)
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=50010,M=999997;
typedef long long ll;
int st[M],id[M];
ll h[M];
int q[M];
struct Circle{
int x,y,r;
}circle[N];
int n,m;
//hash表
ll get_key(int x,int y){
return x*(ll)(1e9+1)+y;
}
int find(int x,int y){
int t=(get_key(x,y)%M+M)%M;
while(h[t]!=-1&&h[t]!=get_key(x,y))
{
t++;
if(t==M) t=0;
}
return t;
}
void bfs(int x0,int y0)
{
int hh=0,tt=0;
int i=find(x0,y0);
st[i]=true;
q[0]=i;
while(hh<=tt){
int t=q[hh++];
int xi=circle[id[t]].x,yi=circle[id[t]].y,ri=circle[id[t]].r;
for(int x=xi-ri;x<=xi+ri;x++)
for(int y=yi-ri;y<=yi+ri;y++)
if(((x-xi)*(x-xi)+(y-yi)*(y-yi))<=ri*ri){
int m=find(x,y);
if(st[m]||!id[m]) continue;
st[m]=true;
q[++tt]=m;
}
}
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++) {
cin>>circle[i].x>>circle[i].y>>circle[i].r;
int t=find(circle[i].x,circle[i].y);
if(h[t]==-1) h[t]=get_key(circle[i].x,circle[i].y);
if(!id[t]||circle[id[t]].r<circle[i].r) id[t]=i;
}
for(int i=0;i<m;i++){
int xi,yi,ri;
cin>>xi>>yi>>ri;
for(int x=xi-ri;x<=xi+ri;x++)
for(int y=yi-ri;y<=yi+ri;y++)
if(((x-xi)*(x-xi)+(y-yi)*(y-yi))<=ri*ri){
int t=find(x,y);
if(st[t]||!id[t]) continue;
bfs(x,y);
}
}
int res=0;
for(int i=1;i<=n;i++){
if(st[find(circle[i].x,circle[i].y)]) res++;
}
cout<<res<<endl;
return 0;
}
*综上:这个题的m,n范围51e4远小于x,y范围1e9,用哈希表来存炸弹坐标,来优化空间。**