06-图2 Saving James Bond - Easy Version（25 分） （数据结构）

06-图2 Saving James Bond - Easy Version（25 分）

This time let us consider the situation in the movie "Live and Let Die" in which James Bond, the world's most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape -- he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head... Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).

Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him whether or not he can escape.

Input Specification:

Each input file contains one test case. Each case starts with a line containing two positive integersN (≤100), the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the (x,y) location of a crocodile. Note that no two crocodiles are staying at the same position.

Output Specification:

For each test case, print in a line "Yes" if James can escape, or "No" if not.

题目大意

在一个二维坐标中有一个边长为100米的正方形地图，007位于坐标为原点啥上的圆形岛上（岛的直径（diameter）为15），周围全是鳄鱼(点），他每次可跳D米，问你007可以逃出这个地图吗? 以案例为例详情如下图。

解题思路：把每个点的坐标存下来，然后进行dfs.

注意：第一跳和以后在鳄鱼身上的跳是不一样的。

详细见代码

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
const int BORDER=50;
const double  ISLAND=15.0/2;
const int N=110;
struct node{
	double x,y;
};
node p[N];//记录鳄鱼的坐标 
bool vis[N];//标记重复 
int n;//输入鳄鱼的个数 
double JUMP;//007每次可以调的距离 
bool FirstJump(int i){//第一次跳是否可以调到鳄鱼身上 
	return sqrt( p[i].x*p[i].x+p[i].y*p[i].y )<=JUMP+ISLAND;
}
bool Jump(int x,int y){//每一次跳（除第一次）是否可以到鳄鱼上 
	return sqrt( (p[x].x-p[y].x)*(p[x].x-p[y].x)+(p[x].y-p[y].y)* ( p[x].y-p[y].y) )<=JUMP;
}
bool judge(int i){//判断007是否逃出 
	return (abs(p[i].x)>=50-JUMP||abs(p[i].y)>=50-JUMP);
}
bool DFS(int i){
	vis[i]=true;
	bool ans=false;
	if(judge(i))
		return true;
	for(int t=0;t<n;t++)
	{
		if(!vis[t]&&Jump(i,t))
			ans=DFS(t);
		if(ans)
			break;
	}
	return ans;
}
void Save007(){
	bool IsSave=false;
	for(int i=0;i<n;i++){//遍历每一点，把每种情况dfs一遍 
		if(!vis[i]&&FirstJump(i)){		
			IsSave=DFS(i);//如果其中有其中情况符合要求，直接退出 
			if(IsSave)
				break;	
		}
	}
	if(IsSave)
		puts("Yes");
	else 
		puts("No");
}
int main()
{
	
	cin>>n>>JUMP;
	for(int i=0;i<n;i++)
		cin>>p[i].x>>p[i].y;
	for(int i=0;i<110;i++)
		vis[i]=false;
	 Save007();
	return 0;
}