浙大数据结构慕课课后题（06-图2 Saving James Bond - Easy Version）(拯救007)

题目要求：

This time let us consider the situation in the movie "Live and Let Die" in which James Bond, the world's most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape -- he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head... Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).

Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him whether or not he can escape.

输入格式： 

Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the (x,y) location of a crocodile. Note that no two crocodiles are staying at the same position. 

输出格式： 

For each test case, print in a line "Yes" if James can escape, or "No" if not. 

样例输入： 

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 

样例输出： 

Yes 

翻译：

题解： 

        思路如注释所示，可通过所有测试点。

#include<bits/stdc++.h>
using namespace std;const int MAX_N = 100;
const int LAKE_R = 50;
const double ISLAND_R = 7.5;  vector<pair<int,int>> cro;  //这里先不固定cro的存储大小，用来节约存储空间与动态调整数组大小 
bool vis[MAX_N];double dis(int x1, int y1, int x2, int y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
} bool canbestart(int x, int y,int D){      //是否能作为DFS搜索的起始点，也就是能从岛屿跳到的第一条鳄鱼 return dis(0, 0, x, y)-ISLAND_R <= D;
}bool success(int x, int y, int D){        //是否能成功跳到岸边 return (abs(x)+D>=LAKE_R)||(abs(y)+D>=LAKE_R);
}bool DFS(int index, int D){vis[index] = true;int x = cro[index].first;int y = cro[index].second;if(success(x, y, D)) return true;for(int i=0; i < cro.size(); i++){if(!vis[i] && dis(x, y, cro[i].first, cro[i].second) <= D){   //如果遍历的点没有搜索过，且从上一个点可以跳到这个点，则加入路线中 if(DFS(i,D)){return true;		}}}return false;
}int main(){int N,D;cin>>N>>D;cro.resize(N);         //把动态数组的大小置为N    fill(vis,vis + N,false);    //把vis的值初始化为0 for(int i=0; i < N; i++){cin>>cro[i].first>>cro[i].second;}//从每个能从湖心岛跳跃到达的鳄鱼开始遍历for(int i=0; i < N; i++){if(!vis[i] && canbestart(cro[i].first,cro[i].second,D)){if(DFS(i,D)){cout<<"Yes"<<"\n";return 0;		}}}	cout<<"No"<<"\n"; 
} 

总结： 

        1.用pair型数据存储一个坐标点，因为它可以包含两个元素。 

        2.每次开始DFS搜索时，注意先看起始点是否已经被其他路径包含过，我第一次做时单纯遍历了每一个能跳到的起始点，上交时出现段错误，后来查阅资料发现这种情况可能会使DFS递归困在一个环形结构中，导致一直申请空间，从而爆栈，这是不对的。

        3.这个题包含了一些数学几何方面的知识，在找第一个起始点时，把起始点与湖心岛圆心的距离与D比较，其实就是圆外一点到圆周上距离的计算。（图上这种情况是可以作为起始点的）

 

        4.判断是否能上岸边，这里我用的方法是看已到达的坐标点的横纵坐标加D是否超过了整个湖的半径。（图上这种情况是上不了岸的）