题目描述
有n个炸雷,有m个排雷火箭,在允许发生连锁反应的条件下,排雷火箭最多可以摧毁多少个炸雷?
算法1
(dfs + 手写哈希) $O(4 * r ^ 2(n + m))$
总体思路:1、首先关于建图,点数太多,直接建图时间复杂度O(n ^ 2),超时,因此,发现每个排雷火箭以及炸雷的爆炸范围很小,因此我们可以枚举每个排雷火箭或炸雷周围半径大小的所有点,判断是否有炸雷,这样建图的时间复杂度O(m * 4 * r * r),当然我们没有必要真的建图出来.只是枚举即可
2、判断是否有炸雷,可以用哈希表unordered_map快速判断,将一个二维坐标转换成唯一的一个1e9 + 1进制的LL类型数值,也可以用map直接存储二维坐标,当然这两种在acwing上是无法ac此题的,超时,在蓝桥杯官网上可以AC.
3、那么接下来就讲一下如何手写哈希表,ac此题
因为x,y坐标范围是0 ~ 1e9,如果我们将x,y看成是1e9 + 1进制的数位中的数字,那么x * 1e9 + 1 + y 一定是唯一的,相当于y是第0位,x是第1位.这样映射转成的LL类型数值一定是唯一的(很妙)
对于同一个位置,可能存在多个炸雷,我们只需要保留半径最大的一个炸雷编号即可,用id数组记录炸雷编号,最后还要标记哪些炸雷被摧毁,用st数组来标记判重
注意:哈希表h的空间至少要开到炸雷数量n的两倍,当然此题可以开到十倍,空间在ok的情况下,开的越大越好,这样哈希表发生冲突的概率越小
由于哈希表的下标表示的是每个二维坐标转换后映射的位置,因此id,st数组也要开和哈希表一样的空间.
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 50010,M = 1e6 + 7;
int n,m;
struct Node
{
int x,y,r;
}t[N];
LL h[M]; // 将每对二维坐标映射到唯一确定的一个1e9 + 1进制的数
int id[M]; // 存储每个炸雷映射到哈希表所在位置上的编号
bool st[M]; // 标记哪些点被摧毁
// 将二维坐标映射到LL数值
LL get_key(int x,int y)
{
return x * 1000000001ll + y;
}
int find(int x,int y)
{
LL key = get_key(x,y);
int k = (key % M + M) % M;
while(h[k] != -1 && h[k] != key)
if( ++ k == M)
k = 0;
return k;
}
int square(int x)
{
return x * x;
}
void dfs(int x,int y,int r)
{
for(int a = x - r;a <= x + r;a++)
for(int b = y - r;b <= y + r;b++)
{
if(h[find(a,b)] != -1 && !st[find(a,b)] && square(a - x) + square(b - y) <= r * r)
{
st[find(a,b)] = true;
dfs(a,b,t[id[find(a,b)]].r);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
memset(h, -1, sizeof h);
for(int i = 1;i <= n;i++)
{
int x,y,r;
scanf("%d%d%d",&x,&y,&r);
t[i] = {x,y,r};
LL k = find(x,y);
if(h[k] == -1) h[k] = get_key(x,y);
// 同一个位置出现多颗炸雷,我们取半径最大的炸雷编号
if(!id[k] || t[id[k]].r < t[i].r)
id[k] = i;
}
while(m -- )
{
int x,y,r;
scanf("%d%d%d",&x,&y,&r);
dfs(x,y,r);
}
int res = 0;
for(int i = 1;i<=n;i++)
if(st[find(t[i].x,t[i].y)])
res ++;
printf("%d\n",res);
return 0;
}