【2022年省赛B组】试题H:扫雷

题解

由于每个点可以存在多个炸雷，可以对于每个$(x, y)$统计一下炸雷的数量，只需要维护最大半径的炸雷即可。 由于$n$数量高达$5\times 10^4$，所有坐标数值范围在$[0, 10^9]$，不可能两两判断是否两个雷之间存在连锁反应。 但是题目条件中$r \leqslant 10$， 这说明每个雷爆炸范围很小，就算对每个雷都暴力枚举半径$r$内所有点的时间复杂度也只有$r^2$级别，可以承受。

因此考虑使用多源BFS算法: 最开始将$M$个排雷火箭$(x_j, y_j, r_j)$塞入BFS的队列中，不断扩展。对于队列中的每个三元组$(x, y, r)$而言：只需要暴力枚举以$x, y$为圆心，$r$为半径中的所有点$(xx, yy)$,判断该位置是否存在新的炸雷即可。

需要判断某位置$(x,y)$是否存在炸雷，因此可以使用$Hahs$来进行一一映射。具体实现：

• map<pair<int,int>, int> R来记录半径：$R[<x, y>] = r$表示坐标为$<x, y>$对应的半径为$r$。
• map<pair<int,int>,int> C来记录炸雷数量，$C[<x, y>]$表示坐标为$<x, y>$的炸雷数量。

提交代码

#include<bits/stdc++.h>
typedef std::pair<int,int> PII;
std::map<PII,int> R, C;
struct Node
{
    int x, y, r;
};

int dist(int x, int y,int i, int j)
{
    return (x - i) * (x - i) + (y - j)* (y - j);
}
int BFS(int m)
{
    std::queue<Node> q;
    int ans = 0;
    for(int i = 0; i < m; i++)
    {
        int a, b, r;
        std::cin >> a >> b >> r;
        q.push({a, b, r});
    }
    while(q.size())
    {
        Node t = q.front();
        q.pop();
        int x = t.x, y = t.y, r = t.r;

        for(int i =  x - r; i <= x + r; i++)
        {
            for(int j = y - r; j <= y + r; j++)
            {
                if(dist(i, j, x, y) > r * r) continue;

                if(R.count(std::make_pair(i, j)) && C[{i, j}])
                {
                    ans += C[{i, j}];
                    C[{i, j}] = 0;
                    q.push({i, j, R[{i, j}]});
                }
            }
        }
        
    }
    return ans;
}
void solve()
{
    int n, m; std::cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        int x, y, r;
        std::cin >> x >> y >> r;
        auto point = std::make_pair(x, y);
        R[point] = std::max(R[point], r);
        C[point] += 1;
    }
    std::cout << BFS(m) << "\n";
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t = 1;
    while(t--) solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
map<PII, int> coordinate, cnt;
/*
coordinate存坐标(x, y)和半径r的映射关系 
cnt存坐标(x, y)和该坐标上炸雷总数的映射关系
*/
int n, m, res;

ll distance(int x1, int y1, int x2, int y2)
{
    return (ll)pow(x1 - x2, 2) + pow(y1 - y2, 2);
}

void bfs()
{
    queue<pair<PII, int>> q;
    for(int i = 0; i < m; i ++ )
    {
        int x, y, r;
        cin>>x>>y>>r;
        q.push({{x, y}, r});
    }

    while(q.size())
    {
        auto u = q.front();
        q.pop();
        int x = u.first.first, y = u.first.second, r = u.second;
        //搜索的时候用r搜 因为r很小很小
        for(int i = x - r; i <= x + r; i ++ )
            for(int j = y - r; j <= y + r; j ++ )
            {
                //如果不在覆盖范围内 continue
                if(distance(x, y, i, j) > r*r)continue;
                auto t = make_pair(i, j);
                //如果这个点上有雷
                if(coordinate.count(t))
                {
                    res += cnt[t];
                    q.push({t, coordinate[t]});
                    coordinate.erase(t);
                }
            }
    }
  
    cout<<res<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i = 1; i <= n; i ++ )
    {
        int x, y, r;
        cin>>x>>y>>r;
        coordinate[{x, y}] = max(coordinate[{x, y}], r);
        //显然如果一个点上 有两个雷 那么有效的是半径大的
        cnt[{x, y}] ++;
    }
    bfs();
    return 0;
}