这一次让我们来考虑一下电影《生死关头》中的情况，在这部电影中，世界上最著名的间谍詹姆斯·邦德被一群毒贩抓获。他被送到一个湖泊中心的一小块土地上，四周有很多鳄鱼。在那里，他采取了最大胆的行动逃跑——他跳到离他最近的鳄鱼的头上!在鳄鱼意识到发生了什么之前，詹姆斯又跳到另一个大脑袋上……最后，他在最后一条鳄鱼咬他之前到达了岸边(实际上，特技演员被鳄鱼的大嘴抓住了，因为他的厚靴子差点没能逃脱)。
假设这个湖是100×100的正方形。假设湖的中心在(0,0)，东北角在(50,50)。中心岛是一个以(0,0)为中心的圆盘，直径为15。湖里有许多鳄鱼在不同的位置。根据每条鳄鱼的坐标和詹姆斯能跳的距离，你必须告诉他是否能逃跑。
Input Specification:
每个输入文件包含一个测试用例。每一种情况都是从一行开始，其中包含两个正整数N(≤100)，鳄鱼的数量，和D，詹姆斯能跳的最大距离。然后是N行，每一行包含一个鳄鱼的(x,y)位置。注意，没有两条鳄鱼会呆在同一位置。
Output Specification:
对于每个测试用例，如果James可以逃跑，则打印一行“Yes”，如果不能，则打印一行“No”。
Sample Input 1:
14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12
Sample Output 1:
Yes
Sample Input 2:
4 13
-12 12
12 12
-12 -12
12 -12
Sample Output 2:
No
思路
初始位置在一个半径为7.5的小岛上，设置初始位置为（0,0），每只鳄鱼视作一个点。利用DFS依次计算两点之间的距离，如果小于等于可以跳跃的距离就跳到这条鳄鱼头上，并计算是否可以从次点处跳到岸上。
起跳处视为（0,0）的话第一跳的起跳距离即为D+7.5，要单独拿出来计算
代码
#include<bits/stdc++.h>
#define MAX 101
using namespace std;
typedef struct Crocodile{
double x,y;
int vis;
}Crocodile;
Crocodile pos[MAX];
double dis;
bool flag=false;//判断是否能跳
//深度优先搜索
void DFS(Crocodile seven,int N,int D){
seven.vis=1;
for(int i=0;i<N+1;i++){
dis=sqrt((pos[i].x-seven.x)*(pos[i].x-seven.x)+(pos[i].y-seven.y)*(pos[i].y-seven.y));
if(D>=dis&&pos[i].vis==0){
pos[i].vis=1;
//cout<<pos[i].x<<" "<<pos[i].y<<endl;
if((50-pos[i].x)<=D||(50-pos[i].x)>=(100-D)||(50-pos[i].y)<=D||(50-pos[i].y)>=(100-D)){
flag=true;
break;
}
DFS(pos[i],N,D);
}
}
}
int main(){
int N;
double D;
cin>>N>>D;
for(int i=1;i<N+1;i++){
cin>>pos[i].x>>pos[i].y;
pos[i].vis=0;//初始设置为未被访问
}
pos[0].x=0;//初始位置
pos[0].y=0;
pos[0].vis=0;
for(int i=0;i<N+1;i++){
dis=sqrt((pos[i].x-pos[0].x)*(pos[i].x-pos[0].x)+(pos[i].y-pos[0].y)*(pos[i].y-pos[0].y));
if((D+7.5)>=dis&&pos[i].vis==0){
if((50-pos[i].x)<=D+7.5||(50-pos[i].x)>=(100-D-7.5)||(50-pos[i].y)<=D+7.5||(50-pos[i].y)>=(100-D-7.5)){
flag=true;
break;
}
DFS(pos[i],N,D);
}
}
if(flag){
cout<<"Yes";
}
else{
cout<<"No";
}
return 0;
}