柚子快報(bào)激活碼778899分享：算法 掃雷（藍(lán)橋杯）
柚子快報(bào)激活碼778899分享：算法 掃雷（藍(lán)橋杯）
題目描述
小明最近迷上了一款名為《掃雷》的游戲。其中有一個(gè)關(guān)卡的任務(wù)如下， 在一個(gè)二維平面上放置著 n 個(gè)炸雷，第 i 個(gè)炸雷 (xi , yi ,ri) 表示在坐標(biāo) (xi , yi) 處存在一個(gè)炸雷，它的爆炸范圍是以半徑為 ri 的一個(gè)圓。
為了順利通過這片土地，需要玩家進(jìn)行排雷。玩家可以發(fā)射 m 個(gè)排雷火箭，小明已經(jīng)規(guī)劃好了每個(gè)排雷火箭的發(fā)射方向，第 j 個(gè)排雷火箭 (xj , yj ,rj) 表示這個(gè)排雷火箭將會(huì)在 (xj , yj) 處爆炸，它的爆炸范圍是以半徑為 rj 的一個(gè)圓，在其爆炸范圍內(nèi)的炸雷會(huì)被引爆。同時(shí)，當(dāng)炸雷被引爆時(shí)，在其爆炸范圍內(nèi)的炸雷也會(huì)被引爆?，F(xiàn)在小明想知道他這次共引爆了幾顆炸雷？?
你可以把炸雷和排雷火箭都視為平面上的一個(gè)點(diǎn)。一個(gè)點(diǎn)處可以存在多個(gè)炸雷和排雷火箭。當(dāng)炸雷位于爆炸范圍的邊界上時(shí)也會(huì)被引爆。
輸入格式
輸入的第一行包含兩個(gè)整數(shù) n、m.
接下來的 n 行，每行三個(gè)整數(shù) xi , yi ,ri，表示一個(gè)炸雷的信息。
再接下來的 m 行，每行三個(gè)整數(shù) xj , yj ,rj，表示一個(gè)排雷火箭的信息。? ? ??
輸出一個(gè)整數(shù)表示答案。
樣例輸入
2 1
2 2 4
4 4 2
0 0 5
樣例輸出
2
提示
示例圖如下，排雷火箭 1 覆蓋了炸雷 1，所以炸雷 1 被排除；炸雷 1 又覆蓋了炸雷 2，所以炸雷 2 也被排除。
對(duì)于 40% 的評(píng)測(cè)用例：0 ≤ x, y ≤ 109 , 0 ≤ n, m ≤ 103 , 1 ≤ r ≤ 10.?
對(duì)于 100% 的評(píng)測(cè)用例：0 ≤ x, y ≤ 109 , 0 ≤ n, m ≤ 5 × 104 , 1 ≤ r ≤ 10.?
第一種
圖的深度優(yōu)先遍歷，鄰接表實(shí)現(xiàn)，? 由于點(diǎn)數(shù)有1e5,那么遍歷所有圖上的點(diǎn)是否聯(lián)通，需要O(n^2)也就是需要2.5e9，? 明顯會(huì)超時(shí)。(WA)
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int N=5e3+10;
bool st[N];
int n,m;
//存炸彈
struct node
{
int x,y,r;
}stu[N];
vector
//判斷是否在這顆雷是否在這個(gè)圓
bool sqr(int x,int y,int xx,int yy,int r)
{
if((xx-x)*(xx-x)+(yy-y)*(yy-y)<=r*r) return true;
return false;
}
//連成一個(gè)連通圖 雷在這個(gè)雷的范圍內(nèi)的就擴(kuò)展
void add(int idx)
{
int x=stu[idx].x,y=stu[idx].y,r=stu[idx].r;
for(int i=1;i<=n;i++)
{
if(i!=idx)
{
if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i);
}
}
}
//看有多少顆符合要求的炸彈
int dfs(int idx)
{
int sum=1;
st[idx]=1;
for(int i=0;i { int j=v[idx][i]; if(!st[j]) { st[j]=1; sum+=dfs(j); } } return sum; } //計(jì)算這顆排雷火箭能炸多少地雷 int dfs_Trave(int x,int y,int r) { int sum=0; for(int i=1;i<=n;i++) { if(sqr(stu[i].x,stu[i].y,x,y,r)) { if(!st[i]) sum+=dfs(i); } } return sum; } signed main() { cin>>n>>m; for(int i=1;i<=n;i++) { int x,y,r;cin>>x>>y>>r; stu[i]={x,y,r}; } for(int i=1;i<=n;i++) { add(i); } int sum=0; for(int i=1;i<=m;i++) { int x,y,r;cin>>x>>y>>r; sum+=dfs_Trave(x,y,r); } cout< return 0; } ? ? 圖的深度優(yōu)先遍歷，鄰接表實(shí)現(xiàn) ? ? 由于點(diǎn)數(shù)有1e5,那么遍歷所有圖上的點(diǎn)是否聯(lián)通，需要O(n^2)也就是需要2.5e9， ? ? 先把坐標(biāo)按x軸從小到大排序，再按y軸從小到大排序 ? ? 當(dāng)許多坐標(biāo)扎堆在同一點(diǎn)的時(shí)候，應(yīng)當(dāng)去掉重復(fù)的點(diǎn)，只留下半徑最大的點(diǎn)。 ? ? 不然建圖的時(shí)候有O(n^2)的時(shí)間復(fù)雜度。 ? ? AC版 #include #include #include #include #include #include #include #define int long long using namespace std; typedef pair const int N=5e4+10; bool st[N]; map int n,m,n1=0; //存炸彈 struct node { int x,y,r,cnt; bool operator < (node const & a) const { if(x!=a.x) return x return y } }stu[N]; /* bool cmp(node xx,node yy) { if(xx.x==yy.x) return xx.y return xx.x }*/ vector //判斷是否在這顆雷是否在這個(gè)圓 bool sqr(int x,int y,int xx,int yy,int r) { if((xx-x)*(xx-x)+(yy-y)*(yy-y)<=r*r) return true; return false; } //連成一個(gè)連通圖 雷在這個(gè)雷的范圍內(nèi)的就擴(kuò)展 void add(int idx) { int x=stu[idx].x,y=stu[idx].y,r=stu[idx].r; for(int i=idx-1;i>=0;i--) { if(r<(x-stu[i].x)) break; if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i); } for(int i=idx+1;i<=n1;i++) { if(r<(stu[i].x-x)) break; if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i); } } //看有多少顆符合要求的炸彈 int dfs(int idx) { int sum=stu[idx].cnt; st[idx]=1; for(int i=0;i { int j=v[idx][i]; if(!st[j]) { st[j]=1; sum+=dfs(j); } } return sum; } //計(jì)算這顆排雷火箭能炸多少地雷 int dfs_Trave(int x,int y,int r) { node e1={x-r,y,r,1},e2={x+r,y,r,1}; int l1=lower_bound(stu+1,stu+1+n1,e1)-stu; int r1=upper_bound(stu+1,stu+1+n1,e2)-stu; int sum=0; for(int i=l1;i<=r1;i++) { if(sqr(stu[i].x,stu[i].y,x,y,r)) { if(!st[i]) sum+=dfs(i); } } return sum; } signed main() { cin>>n>>m; for(int i=1;i<=n;i++) { int x,y,r;cin>>x>>y>>r; int id=mp[{x,y}]; if(id!=0) { stu[id].r=max(stu[id].r,r); stu[id].cnt++; } else { int xx=1; n1++; stu[n1].x=x; stu[n1].y=y; stu[n1].r=r; stu[n1].cnt=1; mp[{x,y}]=n1; } } sort(stu+1,stu+1+n1); for(int i=1;i<=n1;i++) { add(i); } int sum=0; for(int i=1;i<=m;i++) { int x,y,r;cin>>x>>y>>r; sum+=dfs_Trave(x,y,r); } cout< return 0; } 第二種 圖的廣度優(yōu)先遍歷，鄰接表實(shí)現(xiàn) ? ? 由于點(diǎn)數(shù)有1e5,那么遍歷所有圖上的點(diǎn)是否聯(lián)通，需要O(n^2)也就是需要2.5e9， ? ? 先把坐標(biāo)按x軸從小到大排序，再按y軸從小到大排序 ? ? 當(dāng)許多坐標(biāo)扎堆在同一點(diǎn)的時(shí)候，應(yīng)當(dāng)去掉重復(fù)的點(diǎn)，只留下半徑最大的點(diǎn)。 ? ? 不然建圖的時(shí)候有O(n^2)的時(shí)間復(fù)雜度。 AC版 #include #include #include #include #include #include #include #define int long long using namespace std; typedef pair const int N=5e4+10; map bool st[N]; vector int n,m,n1; struct node { int x,y,r,num; bool operator < (node const &a) const { if(x!=a.x) return x return y } }stu[N]; bool sqr(int x1,int y1,int x2,int y2,int r) { if((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)<=r*r) return true; return false; } void add(int idx) { int x=stu[idx].x,y=stu[idx].y,r=stu[idx].r; for(int i=idx-1;i>=0;i--) { if(r<(x-stu[i].x)) break; if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i); } for(int i=idx+1;i<=n1;i++) { if(r<(stu[i].x-x)) break; if(sqr(x,y,stu[i].x,stu[i].y,r)) v[idx].push_back(i); } } int bfs(int idx) { int sum=stu[idx].num; queue q.push(idx); st[idx]=1; while(q.size()) { int t=q.front(); q.pop(); for(int i=0;i { int j=v[t][i]; if(!st[j]) { st[j]=1; sum+=bfs(j); } } } return sum; } int bfs_Trave(int x,int y,int r) { node e1={x-r,y,r,1},e2={x+r,y,r,1}; int l1=lower_bound(stu+1,stu+1+n1,e1)-stu; int r1=upper_bound(stu+1,stu+1+n1,e2)-stu; int sum=0; for(int i=l1;i<=r1;i++) { if(sqr(stu[i].x,stu[i].y,x,y,r)) { if(!st[i]) sum+=bfs(i); } } return sum; } signed main() { cin>>n>>m; for(int i=1;i<=n;i++) { int x,y,r;cin>>x>>y>>r; int xx=mp[{x,y}]; if(xx!=0) { stu[xx].r=max(stu[xx].r,r); stu[xx].num++; } else { n1++; stu[n1]={x,y,r,1}; mp[{x,y}]=n1; } } sort(stu+1,stu+1+n1); for(int i=1;i<=n1;i++) { add(i); } int sum=0; for(int i=0;i { int x,y,r;cin>>x>>y>>r; sum+=bfs_Trave(x,y,r); } cout< return 0; } 柚子快報(bào)激活碼778899分享：算法 掃雷（藍(lán)橋杯） 精彩內(nèi)容
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
Falabella海外時(shí)尚購
