扫雷(哈希+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\) 的一个圆，在其爆炸范围内的炸雷会被引爆。

同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。

现在小明想知道他这次共引爆了几颗炸雷？

你可以把炸雷和排雷火箭都视为平面上的一个点。

一个点处可以存在多个炸雷和排雷火箭。

当炸雷位于爆炸范围的边界上时也会被引爆。

解题思路：

暴力扫描所有可能爆炸的点：

无疑啊，这种暴力的复杂度在O(n\(^2\))的，0<=n<=5e4,肯定会TLE滴

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

哈希+bfs:

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

其中：bfs(O(n)),哈希(O(1))

哈希：map<key,val>

考虑哈希的细节：

二维坐标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
哈希表的长度：已知题目n小于等于5e4，哈希表的长度至少是2n，尽可能的开大空间，避免冲突的发生，同时哈希表的长度应该为一个质数，所以取1e6+7
哈希表的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;

}

扫雷(哈希+bfs)的相关教程结束。