7-10 Saving James Bond - Easy Version (25 分)

这个题主要是审好题目。 下面有两种方法：

一、先将是不是有边，是否与岸有连接算出来

步骤： 1、读入数据，计算输入点是不是可以到岸。 2、对权值初始化，计算各点之间是不是有线。 3、一次DFS搜索，看看是不是能从中心到岸边。

#include <iostream> #include <cmath> using namespace std; int book[101]; //是否访问 int flag = 0; int Flee[101]; //是否可以逃跑 const int INFO = 100000; void DFS(int i,int G[][101],int Nv){ book[i] = 1; if(Flee[i] == 1) flag = 1; for(int j = 0;j <= Nv;j++){ //注意一共Nv+1个点 if(!book[j] && G[i][j] == 1){ DFS(j,G,Nv); } } } int main(){ int x,y; int Nv; //顶点数 int X[101],Y[101]; //顶点坐标 int Dist; //跳的最远距离 int G[101][101]; //是否有边 X[0] = Y[0] = 50; scanf("%d%d",&Nv,&Dist); for(int i = 1;i <= Nv;i++){ //读入X，Y并计算能不能从哪里逃出 scanf("%d%d",&x,&y); X[i] = x + 50; Y[i] = y + 50; if(pow(Y[i],2) <= pow(Dist,2) || pow(X[i],2) <= pow(Dist,2)||\ pow(100-Y[i],2) <= pow(Dist,2) || pow(100-X[i],2) <= pow(Dist,2)) Flee[i] = 1; } for(int i = 0;i <= Nv;i++){ //初始化权值 for(int j = 0;j <= Nv;j++){ if(i == j) G[i][j] = 0; else G[i][j] = INFO; if(pow(X[i]-X[j],2) + pow(Y[i]-Y[j],2) <= pow(Dist,2)){ G[i][j] = 1; G[j][i] = 1; } } } for(int j = 0;j <= Nv;j++){ //中间有一个直径15的陆地 if(pow(X[0]-X[j],2) + pow(Y[0]-Y[j],2) <= pow(Dist+7.5,2)){ G[0][j] = 1; G[j][0] = 1; } } DFS(0,G,Nv); if(flag) printf("Yes\n"); else printf("No\n"); system("pause"); return 0; }

二、在线处理，是不是有边，是否到岸

思路： 主要的思路就是用DFS，由于在湖中心时有一个平台，所以要进行特殊处理。 对于图的结构的选择，可以用也可以不用。图只是一个抽象的结构来帮助我们解题，怎么简单怎么写，不用拘泥于使用什么结构(比如邻接表，邻接矩阵，或者不用图的结构)。

#include <iostream> #include <cmath> using namespace std; struct Graph{ int X,Y; bool book; }; bool IsSave(Graph V,int Dist){ //能否到岸 return (pow(V.X,2) <= pow(Dist,2) || pow(V.Y,2) <= pow(Dist,2) || \ pow(100-V.X,2) <= pow(Dist,2) || pow(100-V.Y,2) <= pow(Dist,2)); } bool IsCanJump(Graph V1,Graph V2,int Dist){ //能否从V1跳到V2 return pow(V1.X-V2.X,2) + pow(V1.Y-V2.Y,2) <= pow(Dist,2); } bool DFS(int index,int Nv,int Dist,Graph G[]){ bool answer = false; G[index].book = true; if(IsSave(G[index],Dist)){ answer = true; } else { for(int i = 1;i <= Nv; i++){ if(!G[i].book && IsCanJump(G[index],G[i],Dist)){ answer = DFS(i,Nv,Dist,G); if(answer == true) break; } } } return answer; } bool IsCenterJump(Graph V,int Dist){ //计算从中心跳出 return pow(V.X-50,2) + pow(V.Y-50,2) <= pow(Dist + 7.5,2); } bool Save007(int Nv,int Dist,Graph G[]){ // 对起点特殊处理 bool answer = false; G[0].book = true; for(int i = 1; i <= Nv; i++){ if(!G[i].book && IsCenterJump(G[i],Dist)){ answer = DFS(i,Nv,Dist,G); if(answer == true) break; } } return answer; } int main(){ int Nv,Dist,x,y; int answer; Graph G[101]; //发生了一次运行时错误,指针越界 G[0].X = G[0].Y = 50; scanf("%d%d",&Nv,&Dist); for(int i = 1; i <= Nv; i++){ scanf("%d%d",&x,&y); G[i].X = x + 50; G[i].Y = y + 50; G[i].book = false; } answer = Save007(Nv,Dist,G); if(answer) printf("Yes\n"); else printf("No\n"); system("pause"); return 0; }