06-图2 Saving James Bond - Easy Version

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:

Sample Output 1:

Yes

Sample Input 2:

Sample Output 2:

No

分析：

根据输入的鳄鱼条数N创建图中的坐标点，用结构体数组表示；
根据当前坐标是否可以直接跳到安全的岸边IsSafe；
遍历数组所有的点，判断哪些可以完成第一步跳跃FirstJump；
完成第一跳后继续深度搜索DFS哪些点可以进行下一跳CanJump；
输出是否存在安全跳到岸边的可能。

编码:

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

#define MAXN 100
#define DIA 15
#define SIDE 100

bool IsSafe(int index);

bool FirstJump(int index);

bool CanJump(int index1, int index2);

bool DFS(int index);

// 1.恶鱼所在坐标数组A，最大为100
// 2.标记数组B，是否是访问过
// 3.恶鱼的条数N, 以及007跳跃的距离D
// 4.池塘边长SIDE为100，中间小岛半径DIA15
struct Data {
    int x, y;
} A[MAXN];
int B[MAXN], N, D;

int main() {
    int i, flag = 0;
    // 1.读取恶鱼的条数，以及007跳跃的距离D
    scanf("%d %d", &N, &D);
    // 2.读取各条恶鱼的坐标，存储在数组A中
    for (i = 0; i < N; i++)
        scanf("%d %d", &A[i].x, &A[i].y);
    // 3.判断是否可以跳到岸边
    if (IsSafe(-1))
        flag = 1;
    else {
        // 4.如不能，则遍历恶鱼寻找可以第一步跳的恶鱼
        for (i = 0; i < N; i++) {
            if (!B[i] && FirstJump(i)) {
                B[i] = 1;
                // 5.如果完成第一跳，继续深度搜索DFS
                if (DFS(i))
                    flag = 1;
            }
        }
    }
    if (flag)
        printf("Yes");
    else
        printf("No");
    return 0;
}

// 是否可以跳到岸边
bool IsSafe(int index) {
    // 1.是否为第一跳-1，小岛半径 + 跳跃距离 > 边长
    if (index == -1) {
        if ((double) DIA / 2 + D >= (double) SIDE / 2)
            return true;
        else
            return false;
    } else {
        // 非第一跳，当前坐标x或y+跳跃距离大于边长，说明成功
        int x = A[index].x;
        int y = A[index].y;
        return (abs(x) + D >= SIDE / 2) || (abs(y) + D >= SIDE / 2);
    }
}

// 是否可以第一跳
bool FirstJump(int index) {
    // 1.坐标x,y到圆心的距离distance
    double distance = sqrt(pow(A[index].x, 2) + pow(A[index].y, 2));
    // 2.如果跳跃距离 + 边长 >= 半径distance，则为真
    return (D + (double) DIA / 2 >= distance);
}

// 是否可以下一跳
bool CanJump(int index1, int index2) {
    int x1 = A[index1].x, y1 = A[index1].y;
    int x2 = A[index2].x, y2 = A[index2].y;
    // 1.取index1,index2两点间的距离distance
    double distance = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
    // 2.如果点距distance小于等于可跳跃的距离
    return D >= distance;
}

// 深度搜索index
bool DFS(int index) {
    // 1.判断是否可以跳到岸边
    if (IsSafe(index))
        return true;
    // 2.遍历数组中所有的点
    for (int i = 0; i < N; i++) {
        // 3.如果点i未被访问过，且点i可以跳跃到，则继续下一跳DFS递归
        if (!B[i] && CanJump(i, index)) {
            B[i] = 1;
            if (DFS(i))
                return true;
        }
    }
    return false;
}

小结：

所有鳄鱼坐标的结构选择，邻接矩阵，邻接表？这个是用结构体数组，或是二维数组；
输入完所有坐标后，开始第一跳时，也需要判断是否可以直接跳到岸边；
求几何运算，如平方、开方、绝对值等，用math库。