拯救007（升级版）

很好的一道bfs题目，到达岸边可以看成是最后一步

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, dist[N], pre[N];
double d, dis;
struct node{
    double x, y;
    int pos;
    double f;
}a[N];
stack<int> sta;

//保证最小的最先搜到
bool cmp(node s1, node s2){
    return s1.f < s2.f;
}

void bfs(){
    queue<node> q;
    memset(dist, 0x3f, sizeof dist);
    //把所有的可能的第一步都给它放进来
    for(int i = 1; i <= n; i++){
        if(a[i].f > 7.5 && a[i].f <= 7.5 + d){
            q.push(a[i]);
            dist[i] = 1;
            pre[i] = -1;
        }
    }
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        int xx = t.x, yy = t.y, poss = t.pos;
        //结束条件，当距离岸边的距离小于等于d时，就准备跳出循环
        if(xx > 0){
            if(yy > 0) dis = min(50.0 - xx, 50.0 - yy);
            else dis = min(50.0 + yy, 50.0 - xx);
        }
        else{
            if(yy > 0) dis = min(50 - yy, 50 + xx);
            else dis = min(50 + yy, 50 + xx);
        }
        if(dis <= d){
            if(dist[n + 1] == 0x3f3f3f3f){
                dist[n + 1] = dist[poss] + 1;
                pre[n + 1] = poss;
                break; 
            }
        }
        for(int i = 1; i <= n; i++){
            if(dist[i] == 0x3f3f3f3f && a[i].f > 7.5){
                double dst = sqrt((xx - a[i].x) * (xx - a[i].x) + (yy - a[i].y) * (yy - a[i].y));
                if(dst <= d){
                    dist[i] = dist[poss] + 1;
                    pre[i] = poss; 
                    q.push(a[i]);
                }
            }
        }
    }
}

void print(int x){
    if(pre[x] == -1){
        sta.push(x);
        return;
    }
    sta.push(x);
    print(pre[x]);
}

signed main(){
    cin >> n >> d;
    for(int i = 1; i <= n; i++){
        cin >> a[i].x >> a[i].y;
        a[i].f = sqrt(1.0 * a[i].x * a[i].x + 1.0 *a[i].y * a[i].y);
    }
    //要考虑一步跳出去的情况
    if(d >= 50){
        cout << 0 << endl;
        return 0;
    }
    //sort这一步非常妙，这样保证了第一步距离最近的点最先被搜索到
    sort(a + 1, a + 1 + n, cmp);
    for(int i = 1; i <= n; i++) a[i].pos = i;
    bfs();
    if(dist[n + 1] == 0x3f3f3f3f){
        cout <<"0" << endl;
        return 0;
    }
    cout << dist[n + 1] << endl;
    print(n + 1);
    //因为搜索的时候，多搜索了最后一步，但是实际上最后一步已经到达岸边
    //所以就不用输出最后一步位置了
    while(sta.size() > 1){
        auto t = sta.top();
        cout << a[t].x <<" " << a[t].y << endl;
        sta.pop();
    }
    return 0;
}

原文地址：http://www.cnblogs.com/N-lim/p/16906958.html