拯救007(DFS)

在老电影“007之生死关头”（Live and Let Die）中有一个情节，007被毒贩抓到一个鳄鱼池中心的小岛上，他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去！（据说当年替身演员被最后一条鳄鱼咬住了脚，幸好穿的是特别加厚的靴子才逃过一劫。）

设鳄鱼池是长宽为100米的方形，中心坐标为 (0, 0)，且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离，你需要告诉他是否有可能逃出生天。

输入格式：

首先第一行给出两个正整数：鳄鱼数量 $N$（≤）和007一次能跳跃的最大距离 $D$。随后 $N$ 行，每行给出一条鳄鱼的 ( 坐标。注意：不会有两条鳄鱼待在同一个点上。

输出格式：

如果007有可能逃脱，就在一行中输出"Yes"，否则输出"No"。

Saving James Bond - Easy Version

判断要点：

    ①湖是一个正方形，边长为100，中心在(0,0)四个定点分别为(50,50),(50,-50),(-50,-50),(-50,50)，湖中小岛直径是15，半径7.5.如果007步长d大于50-7.5=42.5，他就可以直接从小岛跳到湖岸，不经过鳄鱼。

    ②判断007能否从岛上跳到湖中某一点A(x, y)，即d+7.5>=sqrt(x*x+y*y);也就是(d+7.5)*(d+7.5)>=x*x+y*y;

    ③判断007能否从A点直接跳到湖岸，当007步长大于A点到湖岸的距离时，说明可以到达换，即d>= 50-| x | 或者

d>= 50-| y |;

    ④如果跳上一点不能直接跳到湖岸，那就跳上另一点看能不能跳到湖岸满足③条件，这里就是判断能否从A(x1,y1)点跳到B(x2,y2)点，如果007的步长d>=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)),即d*d >= (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)。如果满足，说明可以从A点跳到B点，否则不行。如果不行，就继续递归尝试另一个B点，如果此路不通，返回②条件，换一条路，换一个起点A继续尝试，如果所有路都无法到达对岸，说明无法逃生。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Point {
    int x, y;

    public Point(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }

}

public class Main {
    public static int n, d;
    public static int[] book = new int[101];
    public static List<Point> list = new ArrayList<Point>();

    public static boolean firstJump(int i) { // 第一次跳到第一条鳄鱼，第一个点起点A
        int x = list.get(i).x;
        int y = list.get(i).y;
        if ((d + 7.5)*(d + 7.5) >= (x * x + y * y))
            return true;
        return false;
    }

    public static boolean jump(int j, int i) { // 检测两条鳄鱼之间能否达到
        int x1 = list.get(j).x;
        int y1 = list.get(j).y;
        int x2 = list.get(i).x;
        int y2 = list.get(i).y;
        return d*d >= (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1); // 两点距离公式
    }

    public static boolean isSafe(int i) {
        int x = list.get(i).x;
        int y = list.get(i).y;
        if (x < 0)  x = -x;
        if (y < 0)  y = -y;
        return (d >= 50 - x) || (d >= 50 - y);
    }

    public static int dfs(int j) { //  跳上了第一条鳄鱼
        int ans = 0;
        if (isSafe(j)) { // 此时能否直接跳出池子，判断条件3
            return 1;
        }
        for (int i = 0; i < n; ++i) {
            if (book[i] == 0 && jump(j, i)) { // 判断条件4
                book[i] = 1;
                ans = dfs(i);
                book[i] = 0; // 一条路走不通，会往回走换个点试试
                if (ans == 1)   break;
            }
        }
        return ans;
    }

    public static void solve() {
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (book[i] == 0 && firstJump(i)) { // 检测条件2
                book[i] = 1; // 用过的起点标记一下，返回的时候说明这个起点开始的路走不通，就不用清0了
                ans = dfs(i);
                // book[i] = 0; // 第一步不会往回跳，不用清0
                if (ans == 1) {
                    break;
                }
            }
        }
        if (ans == 1) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    public static void main(String[] args) {

        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        d = cin.nextInt();
        for (int i = 0; i < n; ++i) {
            int x = cin.nextInt();
            int y = cin.nextInt();
            list.add(new Point(x, y));
        }
        cin.close();
        if (d >= 42.5) { // 步长≥42.5，可以直接到湖岸，检测条件1
            System.out.println("Yes");
        } else {
            solve();
        }
    }
}

========================================Talk is cheap, show me the code=======================================