A30297. 拯救 007
题目描述
拯救 007
题目描述
在老电影“007 之生死关头”（Live and Let Die） 中有一个情节， 007 被毒贩抓到一个鳄鱼池中心的小岛上，他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去！（据说当年替身演员被最后一条鳄鱼咬住了脚， 幸好穿的是特别加厚的靴子才逃过一劫。）
设鳄鱼池是长宽为 100 米的方形，中心坐标为 (0, 0)，且东北角坐标为 (50, 50)。 池心岛是以 (0, 0) 为圆心、 直径 15 米的圆。 给定池中分布的鳄鱼的坐标、 以及 007 一次能跳跃的最大距离， 你需要告诉他是否有可能逃出生天。
时间限制： 6000 内存限制： 262144
输入
首先第一行给出两个正整数： 鳄鱼数量 N（≤ 1 00） 和 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
样例#2：
4 13
-12 12
12 12
-12 -12
12 -12
样例输出
样例#1：
Yes
样例#2：
No
参考答案
# include <iostream>
# include <cstring>
using namespace std;
struct node{
int x;
int y;
}s[101];
bool visited[101];
int flag = 0;
bool border(int i, int D)
{
if(s[i].x<= D - 50 || s[i].x >= 50 - D || s[i].y<= D - 50 || s[i].y >= 50 - D)
return 1;
else
return 0;
}
int first(int i , int D)
{
if(s[i].x*s[i].x + s[i].y*s[i].y <= (D+7.5)*(D+7.5))
return 1;
else return 0;
}
int dist(int i, int j , int D)
{
if((s[i].x - s[j].x)*(s[i].x - s[j].x) + (s[i].y - s[j].y)*(s[i].y - s[j].y) <= D*D)
return 1;
else
return 0;
}
int selectdots(int t,int N , int D )
{
visited[t] = 1;
if(border(t , D) == 1)
flag = 1;
for(int i = 0; i<N ; i++)
{
if(!visited[i]&& dist(t , i , D))
flag = selectdots(i , N , D );
}
return flag;
}
int main()
{
int N , D ;
cin>>N>>D;
for(int i=0 ; i<N ;i++)
cin>>s[i].x>>s[i].y;
memset(visited,0,sizeof(visited));
if(D >= 42.5)
cout << "Yes";
else
{
for(int i=0;i<N;i++)
{
if(!visited[i]&&first(i , D))
{
selectdots(i , N , D);
}
}
if(flag == 1)
cout <<"Yes";
else
cout <<"No";
}
return 0;
}答案解析
//方法二
#include <iostream>
#include <cstdio>
#include <cmath>
#define max 102
using namespace std;
struct danger
{
int x,y;
};//定义一个结构体存放每个顶点的坐标
danger p[max]; //定义一个结构体数组来存放所有的点
bool visit[max]={false};
//定义一个全局变量来记录每个点是否已经去过
int n,l;
double dis(danger a,danger b)
{//计算两个点之间的距离，注意添加头文件
return sqrt(pow((a.x-b.x),2)+pow((a.y-b.y),2));
}
void DFS(int v)
{//就是dfs遍历
visit[v]=true;//已经走过这个点就标记一下
if(abs(50-p[v].x)<=l || abs(50-p[v].y)<=l)
{
//如果这个点到边缘的距离是可以跳过去的（往上下左右方向，不是点到点的距离哦）
cout<<"Yes";
exit(0) ;//程序结束输出yes
}
else
{//否则就找下一个能跳的点
for(int i=0;i<n;i++)
{//所有的点都遍历一遍
if(!visit[i] && (dis(p[i],p[v])<=l))
DFS(i);
//如果有顶点没去过而且还可以跳过去的话就从那个点开始重新找下一个点
}
}
}
int main()
{
int num=0;
int first[max];
danger ori;
cin>>n>>l;
for(int i=0;i<n;i++)
{//接收输入数据
cin>>p[i].x>>p[i].y;
}
ori.x=ori.y=0;
for(int i=0;i<n;i++)
{//首先先算一下第一次能跳的点有多少个
if(dis(p[i],ori)<=l+7.5)
{
first[num++]=i;
}
}
if(num==0)
{//如果第一次都没有可以跳的点就直接是no了
cout<<"No";
return 0;
}
for(int i=0;i<num;i++)
{//否则就从这么点开始试试每一条路径
DFS(first[i]);
}
cout<<"No";
}