P8785 [蓝桥杯 2022 省 B] 扫雷 题解

· · 题解

改掉了之前的错误解法，这下应该没问题了。

思路

有一个性质是 r\le 10，也就是一个雷至多引爆 10^2 级别个的位置（不是个数）的雷，而雷的数量级足够我们去暴力寻找这些位置。

将所有炸雷存到一个桶里面，具体的，使用 map 编号，然后存一下在这个位置雷的个数以及这个位置最大的 r。对于每个一个排雷火箭使用 dfs 暴力搜，已经被搜过的地方打个标记就行。

这样复杂度是 O(r^2(n+m)\log n) 的，可以通过此题。

代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk make_pair
using namespace std;
const int N=1e5+5,M=290023;
int n,m,ans,tot;
int cnt[N],tmp[N],vis[N];
map<pii,int> mp;
void dfs(int x,int y,int r){
    for(int i=x-r;i<=x+r;++i){
        for(int j=y-r;j<=y+r;++j){
            if((i-x)*(i-x)+(j-y)*(j-y)>r*r)continue;
            if(mp.count(mk(i,j))){
                int z=mp[mk(i,j)];
                if(vis[z])continue;
                vis[z]=1;ans+=cnt[z];
                dfs(i,j,tmp[z]);
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1,x,y,z,r;i<=n;++i){
        cin>>x>>y>>r;
        if(mp.count(mk(x,y))){
            int z=mp[mk(x,y)];
            ++cnt[z],tmp[z]=max(tmp[z],r);
        }else
            mp[mk(x,y)]=++tot,
            cnt[tot]=1,tmp[tot]=r;
    }for(int i=1,x,y,r,z;i<=m;++i)
        cin>>x>>y>>r,dfs(x,y,r);
    cout<<ans<<'\n';
    return 0;
}