题意
在老电影“007之生死关头”（Live and Let Die）中有一个情节，007被毒贩抓到一个鳄鱼池中心的小岛上，他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去！（据说当年替身演员被最后一条鳄鱼咬住了脚，幸好穿的是特别加厚的靴子才逃过一劫。）
设鳄鱼池是长宽为100米的方形，中心坐标为 (0, 0)，且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离，你需要给他指一条最短的逃生路径 —— 所谓“最短”是指007要跳跃的步数最少。
Input
首先第一行给出两个正整数：鳄鱼数量 N（≤100）和007一次能跳跃的最大距离 D。随后 N 行，每行给出一条鳄鱼的 (x,y) 坐标。注意：不会有两条鳄鱼待在同一个点上。
Output
如果007有可能逃脱，首先在第一行输出007需要跳跃的最少步数，然后从第二行起，每行给出从池心岛到岸边每一步要跳到的鳄鱼的坐标 (x,y)。如果没可能逃脱，就在第一行输出 0 作为跳跃步数。如果最短路径不唯一，则输出第一跳最近的那个解，题目保证这样的解是唯一的。
思路
写的太麻烦了。
大概过程就是在输入的时候计算距离初始点的距离，然后按照该距离排序，将能够到达的点加入队列里。做bfs，每次看是否能够直接跳到岸上，如果可以的话直接结束。否则的话，就遍历所有点，看这些点跟当前点能否可达，可达的话就更新距离。
鳄鱼的坐标从1~n，所以假设岸上的坐标为n+1
每次用pre维护上一个转移过来的点，还原路径的时候从终点递归还原，最后要翻转下路径数组。
注意一下不可达的情况和直接跳到岸上的情况
代码
#include <bits/stdc++.h> using namespace std; const int maxn=1e3+7; #define debug(x) cout<<#x<<":"<<x<<endl; int n,d; struct node{ int x,y; double fit;///第一跳的距离 }a[maxn]; int dis[maxn],pre[maxn]; bool cmp(node a,node b){ return a.fit<b.fit; } bool check(int t){ if(abs(a[t].x)+d>=50) return 1; if(abs(a[t].y)+d>=50) return 1; return 0; } bool check1(int u,int v){ if((a[u].x-a[v].x)*(a[u].x-a[v].x)+(a[u].y-a[v].y)*(a[u].y-a[v].y)<=d*d) return 1; return 0; } void bfs(){ memset(dis,0x3f,sizeof dis); memset(pre,-1,sizeof pre); queue<int>q; for(int i=1;i<=n;i++){ if(a[i].fit>7.5*7.5&&a[i].fit<=(d+7.5)*(d+7.5)){ q.push(i); /// debug(i); dis[i]=1; } } while(!q.empty()){ int t=q.front();q.pop(); ///debug(t); if(check(t)){///能够跳到岸上 if(dis[n+1]==0x3f3f3f3f){ dis[n+1]=dis[t]+1; pre[n+1]=t;return ; } } for(int i=1;i<=n;i++){ if(check1(t,i)){ ///t,i可达 if(dis[i]==0x3f3f3f3f){ q.push(i); dis[i]=dis[t]+1; pre[i]=t; } } } ///debug(dis[t]); /// debug(pre[t]); } } int main() { cin>>n>>d; for(int i=1;i<=n;i++){ cin>>a[i].x>>a[i].y; a[i].fit=a[i].x*a[i].x+a[i].y*a[i].y; } if(d>=42.5){ puts("1");return 0; } sort(a+1,a+1+n,cmp); bfs(); if(dis[n+1]>=0x3f3f3f/2){ puts("0");return 0; } cout<<dis[n+1]<<endl; int t=pre[n+1]; vector<int>tmp; while(t!=-1){ tmp.push_back(t); t=pre[t]; } reverse(tmp.begin(),tmp.end()); ///debug(tmp.size()); for(int i=0;i<tmp.size();i++) cout<<a[tmp[i]].x<<" "<<a[tmp[i]].y<<endl; return 0; } /** 4 13 -12 12 12 12 -12 -12 12 -12 **/
