7-1 拯救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：
代码语言：javascript复制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输出样例 1：
代码语言：javascript复制Yes输入样例 2：
代码语言：javascript复制4 13
-12 12
12 12
-12 -12
12 -12输出样例 2：
代码语言：javascript复制No先来代码吧
代码语言：javascript复制//联通问题
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
struct con{
int x;
int y;
}c[110];
int N,D,vis[110];
int first (int i);
int flag=0;
int saa(int i);
int dfs(int i);
int jump(int i,int j);
//1.接收数组将其存进去 c结构体{int x；int y；}数组c[]
//2.判断是否能一步跳过池子D大于50-7.5
//3.进入深搜dfs，标记访问，先判断能不能跳到下一个鳄鱼，能不能直接上岸（saa）能flag就是1，
//若不能再判断是否没访问过且（first）第一步跳的过去就进入
//该点的递归深搜
//深搜完 判断flag是否为1 1则是yes否则no
int main(){
memset(vis,0,sizeof(vis));
scanf("%d %d",&N,&D);
int i;
for(i=0;i<N;i ){
scanf("%d%d",&c[i].x,&c[i].y);
}
if(D>=50-7.5){
printf("Yesn");
return 0;
}
// 进入深搜dfs
for(i=0;i<N;i ){
if(!vis[i]&&first(i)){
dfs(i);
}
}
if(flag==1)
printf("Yesn");
else
printf("Non");
return 0;
}
int first(int i){
int d1=pow(c[i].x,2);
int d2=pow(c[i].y,2);
int r=(D 7.5)*(D 7.5);
if(r>=d1 d2)
return 1;
return 0;
}
int saa(int i){
if(c[i].x-D<=-50||c[i].x D>=50||c[i].y-D<=-50||c[i].y D>=50)
return 1;
return 0;
}
int jump(int i,int j){
int d1=pow(c[i].x-c[j].x,2);
int d2=pow(c[i].y-c[j].y,2);
int r=D*D;
if(r>=d1 d2)
return 1;
return 0;
}
int dfs(int i){
vis[i]=1;
if(saa(i))//这一点能上岸
flag=1;
for(int j=0;j<N;j ){
if(!vis[j]&&jump(i,j))
flag=dfs(j);
}
return flag;
}说说思路：
- 首先使用结构体
con读入输入数据，包括若干只鳄鱼的坐标和池塘的半径，并将它们存储在数组c中。 - 对于每个鳄鱼，先判断是否能一步跳过池塘（即能否直接上岸）。如果可以，则直接输出
Yes并退出程序。 - 如果不能一步跳过，就进入深搜
dfs。首先标记当前鳄鱼为已访问，然后遍历所有与当前鳄鱼相连的鳄鱼，如果该鳄鱼没有被访问过并且能够通过一步跳跃到达，则进入该鳄鱼的递归深搜。 - 在递归深搜过程中，如果发现某个鳄鱼能一步跳过池塘则将
flag标记为 1。这样，在回溯过程中，只要找到了一个满足条件的鳄鱼，就可以把flag标记为 1，以便后面直接输出Yes。 - 搜索完所有与当前鳄鱼相连的点之后，如果
flag被标记为 1，则说明能跳过池塘，直接输出Yes并退出程序。否则继续搜索下一个没有被访问过的鳄鱼，直到遍历完所有鳄鱼。 - 如果遍历完所有鳄鱼，
flag仍然是 0，则输出No表示不能跳过池塘。
