掃雷

知識點

2024-12-3 藍橋杯每日一題 掃雷 dfs （bfs也是可行的）

題目大意

在一個二維平面上放置這N個炸雷，每個炸雷的信息有$(x_i,y_i,r_i) $，前兩個是坐標信息，第三個是爆炸半徑。然后會輸入M個排雷火箭，同樣的信息；排雷火箭會將范圍內所有的炸雷炸掉，并且會引發一連串爆炸這就要根據爆炸半徑來判斷。

解題思路

1. 要考慮怎么存儲這個炸彈信息，并且還要方便遍歷到。在題目中坐標范圍是$10^9$,肯定不能存到二維數組的平面坐標中。
2. 使用$map<pair<int,int>,vector<int>>$，這樣方便以O(1)的時間訪問到當前位置，并且題目中明確表示同一個點可能會包含多個炸雷或火箭，（這一點一定看清楚），我就是這一點磕了一下；然后就是一定要使用map來定義，unordered_map我用的不行，應為這里使用到了pair。
3. 最后就是遞歸遍歷了，沒輸入一個火箭調用dfs；而且注意到 r 的的范圍是很小的，我們就可以通過遍歷當前位置為中心向四周擴展 r 長度的正方形，然后找到雷之后還要判斷兩點之間的距離是否在園內即可。

Accepted

#include <bits/stdc++.h>
using namespace std;const int N = 5e4+10;
typedef long long ll;
typedef pair<int,int> pii;
int n,m,cnt;
map<pii,vector<int>> a;
// 兩點之間的距離
ll dist(int x1,int y1,int x2,int y2) {return 1ll*(x1-x2)*(x1-x2) + 1ll*(y1-y2)*(y1-y2);
}void dfs(int x,int y,int r) {for(int i = x-r;i <= x+r;i++) {for(int j = y-r;j <= y+r;j++) {if(a.count({i,j})) {int len = a[{i,j}].size();for(int k = 0;k < len;k++) {int rr = a[{i,j}][k];if(rr > 0 && dist(i,j,x,y) <= 1ll*r*r) {a[{i,j}][k] = 0;cnt++;dfs(i,j,rr);}}}}}
}int main()
{int x,y,r;cin>>n>>m;for(int i = 1;i <= n;i++) {cin>>x>>y>>r;a[{x,y}].push_back(r);}while(m--) {cin>>x>>y>>r;dfs(x,y,r);}cout<<cnt;return 0;
}

備注

歡迎大家一起來備戰藍橋杯。可以私信我加聯系方式，人多的話咱就拉個群了。