首页 > 搜索 > BFS搜索 > HDU 4400-Mines-BFS-[解题报告]HOJ
2015
05-24

HDU 4400-Mines-BFS-[解题报告]HOJ

Mines

问题描述 :

Terrorists put some mines in a crowded square recently. The police evacuate all people in time before any mine explodes. Now the police want all the mines be ignited. The police will take many operations to do the job. In each operation, the police will ignite one mine. Every mine has its "power distance". When a mine explodes, any other mine within the power distance of the exploding mine will also explode. Please NOTE that the distance is Manhattan distance here.

More specifically, we put the mines in the Cartesian coordinate system. Each mine has position (x,y) and power distance d.

The police want you to write a program and calculate the result of each operation.

输入:

There are several test cases.
In each test case:
Line 1: an integer N, indicating that there are N mines. All mines are numbered from 1 to N.
Line 2…N+1: There are 3 integers in Line i+1 (i starts from 1). They are the i-th mine’s position (xi,yi) and its power distance di. There can be more than one mine in the same point.
Line N+2: an integer M, representing the number of operations.
Line N+3…N+M+2 : Each line represents an operation by an integer k meaning that in this operation, the k-th mine will be ignited. It is possible to ignite a mine which has already exploded, but it will have no effect.

1<=M<=N<=100000,0<=xi,yi<=10^9,0<=di<=10^9

Input ends with N=0.

输出:

There are several test cases.
In each test case:
Line 1: an integer N, indicating that there are N mines. All mines are numbered from 1 to N.
Line 2…N+1: There are 3 integers in Line i+1 (i starts from 1). They are the i-th mine’s position (xi,yi) and its power distance di. There can be more than one mine in the same point.
Line N+2: an integer M, representing the number of operations.
Line N+3…N+M+2 : Each line represents an operation by an integer k meaning that in this operation, the k-th mine will be ignited. It is possible to ignite a mine which has already exploded, but it will have no effect.

1<=M<=N<=100000,0<=xi,yi<=10^9,0<=di<=10^9

Input ends with N=0.

样例输入:

3
0 0 0
1 1 2
2 2 2
3
1
2
3
0

样例输出:

Case #1:
1
2
0

题目大意是二维坐标系上有一些炸弹,每个炸弹有x,y坐标和爆炸后波及的范围r,这个r指的是跟自己曼哈顿距离r以内的点

就类似于扫雷那样,一个炸弹爆炸可能引起一片一片的炸弹炸出去

然后有一些询问,问点燃某个炸弹后会有多少个炸弹爆炸 已经炸过的就不算了

应该不难想到是用BFS去找临近的点

我的做法是把横坐标离散化,然后每个横坐标建立一个vector,把相应的y都塞进去

然后每次询问,就bfs, 根据每个炸弹的波及范围,如果炸弹横坐标为x,波及范围为r,那么就去找x-r到x+r坐标的vector

然后在vector里寻找相应范围的y

一个lower_bound和一个upper_bound函数就搞定,然后用erase去除爆炸的点

据说正解应该是KD Tree? 不过我不会那种神奇的数据结构,比赛的时候就试着搞了下STL,没想到直接就过了。也许是数据弱?

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
const int maxn = 110005;
const int inf = 2000000005;
struct NODE{
    int y, dis;
    NODE(){
    }
    NODE(int _y, int _dis){
        y = _y; dis = _dis;
    }
    bool operator <(const NODE &tmp)const{
        if(y == tmp.y) return dis < tmp.dis;
        return y < tmp.y;
    }
};
struct POINT{
    int x, y, dis;
    POINT() {
    }
    POINT(int _x, int _y, int _dis){
        x = _x;
        y = _y;
        dis = _dis;
    }
}df[maxn], myque[1111111];
int n, m, hash[maxn], num;
vector<NODE>mygraph[maxn];
void init(){
    num = 0;
    for(int i = 0; i < maxn; i++) mygraph[i].clear();
}
void readdata(){
    for(int i = 1; i <= n ; i++){
        scanf("%d%d%d", &df[i].x, &df[i].y, &df[i].dis);
        hash[num++] = df[i].x;
    }
    sort(hash, hash + num);
    num = unique(hash, hash + num) - hash;
    for(int i = 1; i <= n; i++){
        int id = lower_bound(hash, hash + num, df[i].x) - hash;
        mygraph[id].push_back(NODE(df[i].y, df[i].dis));
    }
}
int fuckit(int fuckid){
    int head = 0, tail = 0, ret = 0;
    vector<NODE>::iterator vectoriterator1, vectoriterator2, tmpvectoriterator;
    myque[tail++] = POINT(df[fuckid].x, df[fuckid].y, df[fuckid].dis);
    while(head < tail){
        POINT now = myque[head++];
        int pos1 = lower_bound(hash, hash + num, now.x - now.dis) - hash;
        int pos2 = upper_bound(hash, hash + num, now.x + now.dis) - hash;
        for(; pos1 != pos2; pos1++){
            int fucknum = hash[pos1];
            int fucky = now.dis - abs(fucknum - now.x);
            int id = lower_bound(hash, hash + num, fucknum) - hash;
            vectoriterator1 = lower_bound(mygraph[id].begin(), mygraph[id].end(), NODE(now.y - fucky, -1));
            vectoriterator2 = upper_bound(mygraph[id].begin(), mygraph[id].end(), NODE(now.y + fucky, inf));
            tmpvectoriterator = vectoriterator1;
            for(; vectoriterator1 != vectoriterator2; vectoriterator1++){
                NODE tmp  = *vectoriterator1;
                myque[tail++] = POINT(fucknum, tmp.y, tmp.dis);
                ret++;
            }
            mygraph[id].erase(tmpvectoriterator, vectoriterator2);
        }
    }
    return ret;
}
int main(){
    int testcases = 0;
    while(scanf("%d", &n) != EOF && n){
        init();
        readdata();
        printf("Case #%d:\n", ++testcases);
        for(int i = 0; i < num; i++) {
            sort(mygraph[i].begin(), mygraph[i].end());
        }
        scanf("%d", &m);
        for(int i = 1; i <= m; i++){
            int k;
            scanf("%d", &k);
            int sum = fuckit(k);;
            printf("%d\n", sum);
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/sdj222555/article/details/8008432


,