Life has its own fate, and meeting may not be accidental.

0%

pta7-13 拯救007 (25分)DFS

7-13 拯救007 (25分)

题目

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

设鳄鱼池是长宽为100米的方形,中心坐标为 (0, 0),且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离,你需要告诉他是否有可能逃出生天。

输入格式:

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

输出格式:

如果007有可能逃脱,就在一行中输出”Yes”,否则输出”No”。

输入样例 1:

1
14 20
2
25 -15
3
-25 28
4
8 49
5
29 15
6
-35 -2
7
5 28
8
27 -29
9
-8 -28
10
-20 -35
11
-25 -20
12
-13 29
13
-30 15
14
-35 40
15
12 12

输出样例1:

1
Yes

输入样例2:

1
4 13
2
-12 12
3
12 12
4
-12 -12
5
12 -12

输出样例2:

1
No

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
struct fun{
4
	int x,y;
5
}great[1000];
6
int vis[1100];
7
int n,m;
8
int flag=0;
9
int first(int i){
10
	int p1=great[i].x*great[i].x;
11
	int p2=great[i].y*great[i].y;
12
	int num=(m+7.5)*(m+7.5);//中心岛跳出
13
	if(p1+p2<=num){
14
		return 1;
15
	} 
16
	return 0;
17
}
18
int key(int x){
19
	if(great[x].x-m<=-50||great[x].x+m>=50||great[x].y-m<=-50||great[x].y+m>=50)
20
		return 1;
21
	return 0;
22
}
23
int jump(int i,int j){//判断能不能跳到下个鳄鱼 
24
	int p1=(great[i].x-great[j].x)*(great[i].x-great[j].x); 
25
	int p2=(great[i].y-great[j].y)*(great[i].y-great[j].y);
26
	if(p1+p2<=m*m)
27
        return 1 ;
28
    return 0;
29
}
30
void dfs(int x){
31
	vis[x]=1;
32
	if(key(x)){	//能直接出去 
33
		flag=1;
34
		return;
35
	}
36
	for(int i=0;i<n;i++){
37
		if(!vis[i]&&jump(x,i)){
38
			dfs(i);
39
		}
40
	}
41
}
42
int main(){
43
	scanf("%d %d",&n,&m);
44
	for(int i=0;i<n;i++){
45
		scanf("%d %d",&great[i].x,&great[i].y);
46
	}
47
	if(m>=50){
48
		printf("Yes\n");
49
	}
50
	else{
51
		memset(vis,0,sizeof(vis));
52
		for(int i=0;i<n;i++){
53
			if(!vis[i]&&first(i)){	//判断第一跳能不能直接出去 
54
				dfs(i);
55
			}
56
		}
57
		if(flag==1)
58
	        printf("Yes\n");
59
	    else
60
	        printf("No\n");
61
    }
62
	return 0;
63
}