返回题解分享
讨论 / 题解分享/ 帖子详情

扫雷(编程题) - 题解

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
struct circle{int x,y,r;};
bool check(circle c,pii p){
int t1 = (c.x - p.first)*(c.x-p.first);
int t2 = (c.y-p.second)*(c.y-p.second);
return c.r >= sqrt(t1+t2);
}
int main() {
int n,m;
cin >> n >> m;
map<pii,pii> mp;//圆心,表示最大半径和对应数量
//处理炸弹
for(int i =1;i <=n;i++){
int x,y,r;cin >> x >> y >> r;
pii p ={x,y};
mp[p].second++;
mp[p].first = max(mp[p].first,r);//最大半径
}
//处理火箭弹
queue<circle> q;
for(int i =1;i <=m;i++){
int x,y,r;cin >> x >> y >>r;
q.push({x,y,r});
}
//记录爆炸坐标
set<pii> s;
//记录答案即爆炸数量
int ans = 0;
//队列,图的搜索
while(!q.empty()){
circle cur = q.front();q.pop();
int x = cur.x,y = cur.y,r = cur.r;
//以i,j为中心,长宽均为2r的正方形范围,正方形更方便
for(int i =x-r;i <= x+r;i++){
for(int j = y-r;j <= y+r;j++){
pii p ={i,j};
//已经爆炸,不处理
if(s.count(p))continue;
//该坐标无雷,不处理
if(!mp.count(p))continue;
//不在范围
if(!check(cur,p))continue;
s.insert(p);
ans +=mp[p].second;
q.push({i,j,mp[p].first});
}
}
}
cout << ans <<endl;
return 0;
}
0 回复 0 转发 0 喜欢 1 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!