浙大数据结构慕课课后题（06-图2 Saving James Bond

浙大数据结构慕课课后题（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"; 
}