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：
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：
Yes
输入样例 2：
4 13 -12 12 12 12 -12 -12 12 -12
输出样例 2：
No
先来代码吧
//联通问题 #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("Yes\n"); return 0; } // 进入深搜dfs for(i=0;i<N;i++){ if(!vis[i]&&first(i)){ dfs(i); } } if(flag==1) printf("Yes\n"); else printf("No\n"); 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表示不能跳过池塘。
