扫雷(哈希+bfs)

扫雷

题目描述：

小明最近迷上了一款名为《扫雷》的游戏。
其中有一个关卡的任务如下：
在一个二维平面上放置着 n 个炸雷，第 i 个炸雷 (x\(_i\),y\(_i\),r\(_i\)) 表示在坐标 (x\(_i\),y\(_i\)) 处存在一个炸雷，它的爆炸范围是以半径为 r\(_i\) 的一个圆。
为了顺利通过这片土地，需要玩家进行排雷。
玩家可以发射 m 个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭 (x\(_j\),y\(_j\),r\(_j\)) 表示这个排雷火箭将会在 (x\(_j\),y\(_j\)) 处爆炸，它的爆炸范围是以半径为 r\(_j\) 的一个圆，在其爆炸范围内的炸雷会被引爆。
同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。
现在小明想知道他这次共引爆了几颗炸雷？
你可以把炸雷和排雷火箭都视为平面上的一个点。
一个点处可以存在多个炸雷和排雷火箭。
当炸雷位于爆炸范围的边界上时也会被引爆。

解题思路：

1. 暴力扫描所有可能爆炸的点：
   无疑啊，这种暴力的复杂度在O(n\(^2\))的，0<=n<=5e4,肯定会TLE滴

考虑到半径0<=r<=10,所以我们考虑能不能只扫描炸弹半径内可能会被引爆的点，那复杂度就会被降下来

2. 哈希+bfs:
   我们将所有的炸弹用哈希映射到到一个唯一的哈希值然后在bfs的过程中，扫描当前炸弹的半径中是否存在炸弹（哈希查找），这样的总复杂度就在O(2r\(^2\)n+2r\(^2\)m)
   其中：bfs(O(n)),哈希(O(1))

哈希：map<key,val>
考虑哈希的细节：

1. 二维坐标x,y唯一映射的哈希值：
   由于x,y的范围为[0,1e9]，所以我们可以将x,y唯一的映射到一个哈希值（x*mod+y),mod = 1e9+1
   这就是将x,y映射为一个1e9+1进制的数，假设这个哈希值为h，那x = h/mod,y = h%mod
2. 哈希表的长度：已知题目n小于等于5e4，哈希表的长度至少是2n，尽可能的开大空间，避免冲突的发生，同时哈希表的长度应该为一个质数，所以取1e6+7
3. 哈希表的key:获取哈希值之后需要将其存入哈希表的一个位置，这个位置就是该哈希值的key。对长度取模即可，若冲突则后移。

代码实现：

# include<bits/stdc++.h>
using namespace std;
# define int long long
const int N = 5e4+10,M = 1e6+7,mod = 1e9+7;
int h[M];//哈希表
int id[M];//对应哈希key的炸弹下标
bool vis[N];//是否被引爆过
struct node{
int x,y,r;
}a[N];
int n,m;

/*
哈希：map<key,value>
*/
int get_hs(int x,int y)//获取哈希值
{
    return (int)x*mod+y;
}
int find(int x,int y)//获取哈希的key
{
    int hs = get_hs(x,y);
    int key = (hs%M+M)%M;
    
    while(h[key] != -1&&h[key] != hs)//如果冲突就后移
    {
        key++;
        if(key == M) key = 0;
    }
    return key;
}

bool check(int x,int y,int r,int a,int b)//是否会被引爆
{
    int d = (x-a)*(x-a)+(y-b)*(y-b);
    return d<=r*r;
}

void bfs(int pos){
    queue<int> q;
    q.push(pos);
    vis[pos] = 1;
    while(q.size()){
        int t = q.front();
        q.pop();
        int x = a[t].x,y = a[t].y,r = a[t].r;
/*
        扫描整个半径内是否存在会被引爆的炸弹
*/
        for(int xx = max(x-r,0ll);xx<=min(x+r,(int)1e9);++xx){
            for(int yy = max(y-r,0ll);yy<=min(y+r,(int)1e9);++yy){
                int key = find(xx,yy);
                if(id[key]&&!vis[id[key]]&&check(x,y,r,xx,yy)){
                    int pos = id[key];
                    vis[pos] = 1;
                    q.push(pos);
                }
            }
        }
    }
}

signed main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    int x,y,r;
    for(int i = 1;i <= n;++i){
        cin>>x>>y>>r;
        a[i] ={x,y,r};
        int key = find(x,y);//获取key
        if(h[key] == -1) h[key] = get_hs(x,y);//存储哈希值
        
        if(!id[key]||a[id[key]].r<r)//如果该点有炸弹，或者有一个半径更大的炸弹
    {
            id[key] = i;
        }
    }
    
    for(int i = 1;i <= m;++i){
        cin>>x>>y>>r;

     // 扫描整个半径内是否存在会被引爆的炸弹

        for(int xx = max(x-r,0ll);xx<=min(x+r,(int)1e9);++xx){
            for(int yy = max(y-r,0ll);yy<=min(y+r,(int)1e9);++yy){
                int key = find(xx,yy);
              //是否有炸弹，是否被引爆过，是否能被引爆
                if(id[key]&&!vis[id[key]]&&check(x,y,r,xx,yy)){
                    bfs(id[key]);
                }
            }
        }
    }
    int ans = 0;
     //扫描答案
    for(int i = 1;i <= n;++i){
        int key = find(a[i].x,a[i].y);
        int pos = id[key];
        if(pos&&vis[pos]) ans++;
    }
    cout<<ans<<endl;
    
    
    return 0;
}