拯救007 升级版-PAT-最短路-axuhongbo的个人博客

7-5 拯救007（升级版）（30 分)

在老电影“007之生死关头”（Live and Let Die）中有一个情节，007被毒贩抓到一个鳄鱼池中心的小岛上，他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去！（据说当年替身演员被最后一条鳄鱼咬住了脚，幸好穿的是特别加厚的靴子才逃过一劫。）

设鳄鱼池是长宽为100米的方形，中心坐标为 (0, 0)，且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离，你需要给他指一条最短的逃生路径 —— 所谓“最短”是指007要跳跃的步数最少。

输入格式：

首先第一行给出两个正整数：鳄鱼数量 $N$ （ $\leq 100$ ）和007一次能跳跃的最大距离 $D$ 。随后 $N$ 行，每行给出一条鳄鱼的 $(x, y)$ 坐标。注意：不会有两条鳄鱼待在同一个点上。

输出格式：

如果007有可能逃脱，首先在第一行输出007需要跳跃的最少步数，然后从第二行起，每行给出从池心岛到岸边每一步要跳到的鳄鱼的坐标 $(x, y)$ 。如果没可能逃脱，就在第一行输出 0 作为跳跃步数。如果最短路径不唯一，则输出第一跳最近的那个解，题目保证这样的解是唯一的。

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

My 修改AC code：

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
double x[200],y[220];
const int inf  =0x3f3f3f3f;
struct node{
 double x,y;
 int i;
 int s;
}a[500];
   int n;
   double D;
   int b[500];
double dis(double x,double y,double x1,double y1){
  return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
}
int pre[500];
 node u;
 int pan(double x,double y){


   if(fabs(x+D)>=50||fabs(y+D)>=50||fabs(x-D)>=50||fabs(y-D)>=50)return 1;
   return 0;
 }
 int vis[520];
 int cmp1(int x)
{
    if((a[x].x*a[x].x+a[x].y*a[x].y)<=(D+7.5)*(D+7.5))return (int)(a[x].x*a[x].x+a[x].y*a[x].y);
     return 0;
}
bool cmp(int a,int b)
{
    return cmp1(a)<cmp1(b);
}
void bfs(){
    queue<node>o;
    memset(vis,0,sizeof vis);
    memset(pre,-1,sizeof pre);
    node oo;
//    oo.x =0;
//    oo.y = 0;
//    oo.s =0;
//    oo.i = 0;
//    vis[0] = 1;
//    o.push(oo);
    for(int i=1; i<=n; i++)
    {

        b[i] = i;
    }
    sort(b+1,b+1+n,cmp);
     for(int i=1; i<=n; i++)
    {
        int h = b[i];
        if(cmp1(h))
        {
            node oo;
            oo.x =a[h].x;
            oo.y = a[h].y;
            oo.s =2;
            oo.i = h;
            //vis[0] = 1;
            o.push(oo);
            vis[h] = 1;
            pre[h] = 0;
        }
    }
    u.i = -1;
    while(!o.empty()){

        node p = o.front();
        o.pop();
       // cout<<p.i<<" "<<p.s<<endl;
        if(pan(p.x,p.y)){

            u = p;
            break;

        }
        for(int i=1;i<=n;i++){

            if(vis[a[i].i])continue;
              if(dis(p.x,p.y,a[i].x,a[i].y)<=D){

                node tt;
                tt.x = a[i].x;
                tt.y = a[i].y;
                tt.i = a[i].i;
                tt.s =  p.s+1;
                o.push(tt);
                vis[a[i].i] =1;
                pre[a[i].i] =p.i;
              }

        }
    }
}

int main()
{



    cin>>n>>D;
    for(int i=1;i<=n;i++){
       cin>>a[i].x>>a[i].y;
       a[i].i = i;
    }
    //printf("0\n");
    bfs();
    if(D>=42.5){

        cout<<1<<endl;
        return 0;
    }
    if(u.i==-1){

        printf("0\n");
    }
    else{
        cout<<u.s<<endl;
        int ppre = u.i;
        stack<int>ans;


        while(ppre!=-1){

            if(ppre==0)break;
        //    cout<<a[ppre].x<<" "<<a[ppre].y<<endl;
            ans.push(ppre);
            ppre =  pre[ppre];
        }
        while(!ans.empty()){

            ppre = ans.top();
            ans.pop();
            cout<<a[ppre].x<<" "<<a[ppre].y<<endl;
        }
    }


    return 0;
}


Right code：


#include "iostream"
#include "math.h"
#include "queue"
#include "stack"
#include "algorithm"
using namespace std;
int n, m;
#define MINLEN 42.5
struct Pointer {
    int x;
    int y;
}point[101];
bool answer = false; /* 记录007能否安全逃生~~ */
bool visited[101] = { false }; /* 判断当前点是否被访问过 */
int path[101] = {-1}; /* 记录跳跃过程中踩过的鳄鱼 */
bool isSave(int x) { /* 判断从当前点能否跳到岸上 */
    if ((point[x].x - m <= -50) || (point[x].x + m >= 50) || (point[x].y - m <= -50) || (point[x].y + m >= 50))
        return true;
    return false;
}

bool jump(int x, int y) { /* 判断2个点距离是否在跳跃能力内 */
    int p1 = pow(point[x].x - point[y].x, 2);
    int p2 = pow(point[x].y - point[y].y, 2);
    int r = m * m;
    if (p1 + p2 <= r)
        return true;
    return false;
}

int firstJump(int x) {  /* 当007处于孤岛时 第一次可以选择跳的鳄鱼 因为第一次判断能否跳跃的计算方法与后面dfs不相同 所以要单独写 */
    int p1 = pow(point[x].x, 2);
    int p2 = pow(point[x].y, 2);
    int r = (m + 7.5) * (m + 7.5);
    if (p1 + p2 <= r) {
        return p1+p2;
    }
    return 0;
}
bool cmp(int a,int b) {
    return firstJump(a) < firstJump(b);
}
void bfs() { /* 用bfs来判断最少要踩几个小鳄鱼才能上岸 */
    int b[101];
    queue<int>q; 
    /* 将第一步能踩到的鳄鱼按距离从小到大的顺序进队列~ 因为输出结果要保证在踩的鳄鱼数量相等的情况下 输出第一步距离最短的~~*/
    for (int i = 0; i < n; i++) {
        b[i] = i;
    }
    sort(b, b + n, cmp); /* 按照第一步的距离排序~~~ */
    int last;
    for (int i = 0; i < n; i++) {
        if (firstJump(b[i])) { /* 能跳上去！ */
            q.push(b[i]);
            visited[b[i]] = true; /* 指向当前层数最后一个数~ */
            last = b[i];
        }
    }
    int step = 2;  /* 记录最少要跳跃的次数 */
    int tail; 
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        if (isSave(p)) {
            int k = 1;
            stack<int> s;
            cout << step << endl;
            while (k < step) {
                //cout << point[p].x << " " << point[p].y << endl;
                s.push(p);
                p = path[p];
                k++;
            }
            while (!s.empty()) {
                p = s.top();
                s.pop();
                cout << point[p].x << " " << point[p].y << endl;
            }
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i] && jump(p, i)) { /* 没踩过并且能跳到 */
                q.push(i);
                path[i] = p; /* 记得当前进队节点的父节点~ */
                visited[i] = true;
                tail = i; /* 指向下一层的最后一个元素 */
            }
        }
        if (last == p) { /* 即将进入下一层~ */
            step += 1;
            last = tail;
        }
    }
    if (q.empty()) { /* 如果队列为空  说明没跳出去啊~ */
        cout << "0" << endl;
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> point[i].x >> point[i].y;
    }
    if (m >= MINLEN) { /* 可以直接从孤岛上提到岸上 直接输出 */
        cout << "1" << endl;
        return 0;
    }
    bfs();
    return 0;
}

my code：

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
double x[200],y[220];
const int inf  =0x3f3f3f3f;
struct node
{
    double x,y;
    int i;
    int s;
} a[500];
int n,D;
double dis(double x,double y,double x1,double y1)
{
    return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
}
int pre[500];
node u;
int pan(double x,double y)
{


    if(fabs(x+D)>=50||fabs(y+D)>=50)return 1;
    return 0;
}
int vis[320];
vector<node>aa;
int ttop =1,tttop=-1;
void bfs()
{
    queue<node>o;
    memset(vis,0,sizeof vis);
    memset(pre,-1,sizeof pre);
    node oo;
    oo.x =0;
    oo.y = 0;
    oo.s =0;
    oo.i = 0;
    vis[0] = 1;
    o.push(oo);
    u.i = -1;
    while(!o.empty())
    {

        node p = o.front();
        o.pop();
        // cout<<p.i<<" "<<p.s<<endl;
        if(pan(p.x,p.y))
        {

            u = p;
            if(ttop)
            {
                tttop =  u.s;
                ttop =0;

            }

            aa.push_back(u);

        }
        for(int i=1; i<=n; i++)
        {

            if(vis[a[i].i])continue;
            if(dis(p.x,p.y,a[i].x,a[i].y)<=D)
            {

                node tt;
                tt.x = a[i].x;
                tt.y = a[i].y;
                tt.i = a[i].i;
                tt.s =  p.s+1;
                o.push(tt);
                vis[a[i].i] =1;
                pre[a[i].i] =p.i;
            }

        }
    }
}

int main()
{



    cin>>n>>D;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].x>>a[i].y;
        a[i].i = i;
    }
    //printf("0\n");
    bfs();
    if(u.i==-1)
    {

        printf("0\n");
    }
    else
    {


        //cout<<aa.size()<<endl;
        double AA =inf;
        for(node kk:aa)
        {

            if(kk.s==tttop)
            {
                int pp = kk.i;
                while(pp!=-1)
                {

                    if(pp==0)break;
                    //    cout<<a[ppre].x<<" "<<a[ppre].y<<endl;
                    //ans.push(ppre);
                    if(pre[pp]==0){

                        if(dis(0,0,a[pp].x,a[pp].y)<AA){
                            AA = dis(0,0,a[pp].x,a[pp].y);
                            u = kk;
                        }
                    }
                    pp =  pre[pp];
                }
            }
        }

        cout<<u.s+1<<endl;
        int ppre = u.i;
        stack<int>ans;


        while(ppre!=-1)
        {

            if(ppre==0)break;
            //    cout<<a[ppre].x<<" "<<a[ppre].y<<endl;
            ans.push(ppre);
            ppre =  pre[ppre];
        }
        while(!ans.empty())
        {

            ppre = ans.top();
            ans.pop();
            cout<<a[ppre].x<<" "<<a[ppre].y<<endl;
        }
    }


    return 0;
}