(第十三届蓝桥杯省赛)H：扫雷（搜索+哈希）

分析：由于这道题目炸弹的分布比较广而且数目也比较多，我们不能够直接建立炸弹与炸弹之间的联系，我们发现每个炸弹的范围都比较小，所以我们可以从炸弹范围入手开始搜索，这道题就是利用排雷火箭去搜索他管辖范围内的所有点，如果有炸弹就用炸弹再去递归搜索他爆炸范围内的炸弹，由于每个炸弹可能会被重复搜索，所以我们需要加一个vis数组，记录每个炸弹是否被搜到过，但是我们这就发现一个问题，就是炸弹的可能位置是很大的，不可能直接开数组去存，所以只能将一个二维的点哈希处理一下，由于最大x值是1e9,我们只要将(x,y)映射成x*(1e9+1)+y即可完成二维到一维的一一映射，再将映射后的值哈希存一下即可，由于每个位置可能会有多个炸弹，而我们搜索到一个位置有炸弹后，我们需要用这个位置的所有炸弹都去搜索一遍吗？其实也不是，我们只需要用爆炸范围最大的那个炸弹去搜索就可以了，因为爆炸范围小的炸弹所能引爆的炸弹一定能被爆炸范围更大的炸弹引爆，所以每个位置我们可以记录一个r，里面存储的是该处所有炸弹的最大爆炸范围，如果没有炸弹那么爆炸范围就视为0.

由于最大多有5e4个炸弹，所以只需要对这些点进行哈希，我们一般哈希数组开10倍左右比较好，但是一般是选择一个质数。

这就是这道题目的思路了，详情见代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=5e4+10,mod=500003;
ll h[mod],ne[mod],e[mod],idx;
int r[mod];
bool vis[mod];
struct node{
	int x,y;
}p[N];//炸弹信息 
int query(int x,int y)//哈希
{
	ll key=(ll)x*1000000001+y;
	int t=(key%mod+mod)%mod;//t为(x,y)的哈希值 
	for(int i=h[t];i!=-1;i=ne[i])
		if(e[i]==key)
			return i;//返回key对应的哈希编号
	return -1;
}
void insert(int x,int y)
{
	ll key=(ll)x*1000000001+y;
	int t=(key%mod+mod)%mod;//t为(x,y)的哈希值 
	e[idx]=key;
	ne[idx]=h[t];
	h[t]=idx++;
}
int sqr(int x)
{
	return x*x;
}
void dfs(int x, int y, int rr)//利用一个炸弹去搜索他所炸范围内的其他炸弹 
{
    vis[query(x,y)]=true;
    for(int i=x-rr;i<=x+rr;i++)
        for(int j=y-rr;j<=y+rr;j++)
            if(sqr(i-x)+sqr(j-y)<=sqr(rr))
            {
                int t=query(i,j);
                if(t==-1) continue;//该点无炸弹 
                if(!vis[t])//t这个位置有炸弹且还没被搜过，利用这个炸弹进行搜索
                    dfs(i,j,r[t]);
            }
}
int main()
{
	memset(h,-1,sizeof h);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int x,y,rr;
		scanf("%d%d%d",&x,&y,&rr);
		p[i]={x,y};//存下炸弹信息，用于最后判断所引爆的炸弹的次数
		int t=query(x,y);
		if(t==-1)//该位置没有炸弹，记录上 
		{
			insert(p[i].x,p[i].y);
			t=query(x,y);
		}
		if(r[t]<rr)
			r[t]=rr;//保留某个点的最大半径，可能这个地方之前有炸弹，我们只需要保存爆炸范围最大的炸弹半径即可 
	}
	while(m--)
    {
        int x,y,rr;
        scanf("%d%d%d",&x,&y,&rr);
        for(int i=x-rr;i<=x+rr;i++)//搜索第 
            for(int j=y-rr;j<=y+rr;j++)
                if(sqr(i-x)+sqr(j-y)<=sqr(rr))
                {
                    int t=query(i,j);
                    if(t==-1) continue;//该点无炸弹 
                    if(!vis[t])//t这个位置有炸弹且还没被搜过，利用这个炸弹进行搜索
                        dfs(i,j,r[t]);
                }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        if(vis[query(p[i].x,p[i].y)])//如果这个位置被搜过就计入答案，被搜过的炸弹都是可以被引爆的 
            ans++;
    printf("%d
",ans);
	return 0;
}