題意:?
? ? ? 煤礦爆炸,每個煤礦有自己的x,y,d,d是他爆炸后會是d距離內的爆炸,每次輸入一個爆炸的煤礦,問你這個煤礦爆炸會有多少個煤礦爆炸.


思路:

? ? ? 爆炸的過程就是搜索的過程,被當前煤礦弄爆炸的煤礦可能繼續去吧別的煤礦蹦爆炸,所以是搜索的過程,但直接搜會超時,所以各種STL,估計是數據水,不然我人感覺STL碰到坑人數據也得N^2,一樣跪,思路是按照x離散化,1 2 3 3 4 離散化成1 2 3 4,然后每個點建立一個multiset,然后把y 和 id塞進去,按照y排序,像上面的那組,1 2 4的set里就一組數據,而3里面有兩組,每次詢問的時候,先找到x的范圍, x - d ,x + d,可以二分或者直接STL,然后再在找到的范圍里找出滿足條件的y,直接STL,這個地方二分會有點復雜,但如果想二分絕對可以,然后就這樣廣搜就行了....

#include<stdio.h> #include<string.h> #include<queue> #include<set> #include<algorithm>#define N 100000 + 100 using namespace std;typedef struct NODE {int y ,id;NODE(int id_ ,int y_){y = y_;id = id_;}bool operator < (const NODE &c) const { return y < c.y; } }NODE; typedef struct {int x ,y ,d; }NOD;int abss(int a) {return a < 0 ? -a : a; }NOD node[N]; int X_hash[N] ,hash_n; int mark[N]; multiset<NODE>SET[N];int BFS(int s) {int ans = 0;if(mark[s]) return ans;mark[s] = 1;queue<int>q;q.push(s);multiset<NODE>::iterator yl,yr,it; while(!q.empty()){ ans ++;int tou ,xin;tou = q.front();q.pop();int xl = lower_bound(X_hash ,X_hash + hash_n ,node[tou].x - node[tou].d) - X_hash;int xr = upper_bound(X_hash ,X_hash + hash_n ,node[tou].x + node[tou].d) - X_hash;for(int i = xl ;i < xr ;i ++){int yy = node[tou].d - abss(node[tou].x - X_hash[i]);yl = SET[i].lower_bound(NODE(0 ,node[tou].y - yy));yr = SET[i].upper_bound(NODE(0 ,node[tou].y + yy));for(it = yl ;it != yr ;it++){if(!mark[it->id]){mark[it->id] = 1;//ans ++; q.push(it->id);}}SET[i].erase(yl ,yr); }}return ans; }int main () {int i ,j ,n ,m ,cas = 1;while(~scanf("%d" ,&n) && n){for(i = 0 ;i < n ;i ++){scanf("%d %d %d" ,&node[i].x ,&node[i].y ,&node[i].d);X_hash[i] = node[i].x;}sort(X_hash ,X_hash + n);hash_n = unique(X_hash,X_hash + n) - X_hash;for(i = 0 ;i < hash_n ;i ++)SET[i].clear();for(i = 0 ;i < n ;i ++){int id = lower_bound(X_hash ,X_hash + hash_n ,node[i].x) - X_hash; //int xl = lower_bound(X_hash + 1 ,X_hash + hash_n + 1 ,node[tou].x - node[tou].d) - X_hash; SET[id].insert(NODE(i ,node[i].y));}scanf("%d" ,&m);printf("Case #%d:\n",cas ++); memset(mark ,0 ,sizeof(mark)); for(i = 1 ;i <= m ;i ++){int id;scanf("%d" ,&id);printf("%d\n" ,BFS(id-1)); } } return 0; }

總結

以上是生活随笔為你收集整理的hdu4400 BFS+STL的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。