2 条题解

  • 1
    @ 2024-3-24 17:33:19
    #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;
    }
    

    信息

    ID
    973
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    48
    已通过
    7
    上传者