这个要用map 判重，扫描每一个进队列的炸弹能够扫到的范围
我自己写的这个会超时，只能过40%的数据，不想自己做优化了，具体优化就是，再开一个map记录当前点的炸弹数量，然后存炸弹信息的时候只存最大的那一个，
#include<iostream> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<vector> #include<math.h> using namespace std ; typedef long long LL ; typedef pair<int,int> PII ; struct node{ LL x , y , r ; node(LL xx,LL yy , LL rr){ x = xx , y = yy , r = rr ; } bool operator < (const node &o) const { if(x == o.x) return y < o.y ; else if(y == o.y) return r < o.r ; else return x < o.x ; } }; queue<node> q ; map<node,bool> mp ; vector<node> a ; vector<node> b ; LL n , m ; LL ans ; LL getdis(int x1,int y1,int x2,int y2){ return (x1-x2)*(x1-x2) + (y1-y2) * (y1 - y2) ; } void bfs(){ for(int i = 0 ; i < m ; i ++){ q.push(b[i]) ; } while(!q.empty()){ node now = q.front() ; q.pop() ; LL x = now.x , y = now.y , r = now.r; for(int i = 0 ; i < n ; i ++){ LL tx = a[i].x , ty = a[i].y , tr = a[i].r ; node g(tx,ty,tr) ; if(mp[g]) continue ; LL dis = getdis(x,y,tx,ty) ; if(r * r >= dis){ q.push(g) ; mp[g] = 1 ; //cout << mp[g] << endl ; ans ++ ; } } } } int main(){ cin >> n >> m ; for(int i = 0 ; i < n ; i ++){ LL x,y,z ; cin >>x >>y >> z ; a.push_back(node(x,y,z)) ; } for(int i = 0 ; i < m ; i ++){ LL x,y,z ; cin >>x >>y >> z ; b.push_back(node(x,y,z)) ; } bfs() ; cout << ans << endl ; return 0 ; } // for (int i = x - r; i <= x + r; i ++ ) //寻找爆炸范围内的雷 // for (int j = y - r; j <= y + r; j ++ ) // { // if (getdis(x, y, i, j) > r * r) continue; // auto s = make_pair(i, j); // if (mie.count(s)) // { // res += cnt[s]; // q.push({s, mie[s]}); //排到的雷看作新的排雷火箭 // mie.erase(s); // } // }
