第十三届蓝桥杯省赛B组 第8题(布响丸啦)

题目 题意: 给定n个二维平面的地雷，给定m个导弹，可以引爆半径r以内的地雷，而半径r以内的地雷又可能引爆其半径r内的其他地雷。问最多能引爆多少个地雷。 思路: dfs或者bfs叭.  用unordered_map 记录对应位置的地雷，只需要记录对应坐标的地雷个数和最大半径即可。 因为unordered_map不支持用pair作key，可以做一个偏移，(1e9+1)x+y作为key，也可以唯一识别，至少比map快多了。 然后还可以减少点枚举，比如不用2r2r的枚举，x枚举2r，y从起点左右试探。 还有就是涨知识的是直接调用mp[x]会比较慢，不如判断mp.find(x) == mp.end() 时间复杂度: O(Πr*r(n+m)),还有哈希的常数。 代码源能过，acwing过不了，不管了，摆烂咧. 代码:

#include
using namespace std;
typedef long long ll;
typedef pair PII;
const int N = 5e4+10;
#define mem(a,x) memset(a,x,sizeof(a))
#define fir(i,a,b) for(int i=a;i 1ll*r*r) break;
		        ll wh = fun(tx,j);
		        if(mp.find(wh) != mp.end())
		        {
		        	int t = mp[wh];
		        	if(t && !vis[t])
		        	{
		        		dfs(t);
		        	}
		        }
			}
		}
}
int cnt = 0;
void solve()
{
    read(n); read(m);
    for(int i=0;i