数据结构刷题笔记3——拯救詹姆斯邦德

06-图2 Saving James Bond - Easy Version (25 分)

题目描述

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.

Input Specification:

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.

Output Specification:

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

Sample Input 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

Sample Output 1:

Yes

Sample Input 2:

4 13
-12 12
12 12
-12 -12
12 -12

Sample Output 2:

No

谷歌翻译版题目描述

06-图2 拯救詹姆斯邦德 - 简易版（25分）

这一次让我们考虑一下电影《生与死》中世界上最著名的间谍詹姆斯邦德被一群毒贩抓获的情况。他被送到了一个充满鳄鱼的湖中心的一小块土地上。在那里，他做出了最大胆的逃跑动作——跳到了最近的鳄鱼的头上！还没等那只动物意识到发生了什么事，詹姆斯又跳到了下一个大脑袋上…… 终于在最后一条鳄鱼咬到他之前到达了岸边（实际上特技演员被大嘴卡住了，他的超厚靴子勉强逃过一劫）。

假设湖是一个 100 x 100 的正方形。假设湖的中心在 (0,0)，东北角在 (50,50)。中央岛是一个以(0,0)为中心、直径为15的圆盘。湖中有许多鳄鱼在不同的位置。给定每条鳄鱼的坐标和詹姆斯可以跳跃的距离，你必须告诉他是否可以逃脱。

输入规格：

每个输入文件包含一个测试用例。每个案例都以一行包含两个正整数 N（≤100）、鳄鱼的数量和 D（詹姆斯可以跳跃的最大距离）开始。然后是 N 行，每行都包含鳄鱼的 (x,y) 位置。请注意，没有两条鳄鱼停留在同一位置。

输出规格：

对于每个测试用例，如果 James 可以逃脱，则打印“Yes”，否则打印“No”。

题目理解与思路

本题提供的数据为每个鳄鱼所在的点的坐标，使用DFS和BFS都能实现，感觉总体难点在于存储这些鳄鱼所在的点的数据结构，刚开始时我使用了一个点类来存储，开辟了一系列的含有坐标的点组成的数组，然后通过遍历这个数组来进行DFS，后来发现了更简单的方法，使用两个全局的数组来分别存储这些点的X坐标和Y坐标，然后数组的下标即表示一个点，所以就不用封装到结构里（PS：主要是我对struct不是很熟悉，写着总是报错。。。）

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define MaxN 101

int DIS,NUM;
int X[MaxN] = {0};
int Y[MaxN] = {0};
int Visited[MaxN] = {0};

int Distance(int i,int j)
{
    return sqrt(pow(X[i]-X[j],2) + pow(Y[i]-Y[j],2));
}

int DFS(int N)
{
    Visited[N] = 1;
    int i;
    if(X[N] >= 50-DIS||X[N] <= DIS-50
       ||Y[N] >= 50-DIS||Y[N] <= DIS-50)//满足边界条件，即能跳到岸边，就返回真，退出
        return 1;
    for(i = 1;i <= NUM; i++)//要从1开始遍历（因为用了0来存储原点，第一个点从1开始）
    {
        if(Visited[i] == 0&& ( Distance(N,i) <= DIS))
            if(DFS(i))
            {
                return 1;
            }
    }
    return 0;
}

int main()
{
    int i;
    scanf("%d %d\n",&NUM,&DIS);
    for(i = 1;i <= NUM; i++)
    {
        scanf("%d %d\n", &X[i],&Y[i]);
    }
    if(DIS+15>=50) {
        printf("Yes\n");
        return 0;
    }
    for(i = 1;i <= NUM;i++)
    {
        if(Distance(0,i) <= 15 + DIS)//第一跳，判断原点距离与第一个点的距离来判断是否能跳上去
        {
            if(DFS(i))
            {
                printf("Yes\n");
                return 0;
            }
        }
    }
    printf("No\n");
    return 0;
}