PAT 圖論題「Saving James Bond」：DFS 判斷鱷魚池逃生路徑

題目大意

詹姆斯·邦德被困在湖中心小島 (半徑 7.5m，即直徑 15m)，湖為 100×100 正方形 (中心 (0,0)，邊界 ±50)。湖中有 N ≤ 100 隻鱷魚，邦德最大跳躍距離 D。判斷能否跳上岸 (邊界距離 ≤ D)。

關鍵幾何判斷

• 第一跳：從島邊 (距原點 7.5m) 到鱷魚，距離 ≤ D → dist(0,0, x,y) ≤ D + 7.5
• 後續跳：鱷魚間距離 ≤ D
• 上岸條件：鱷魚到邊界距離 ≤ D → |x| ≥ 50-D 或 |y| ≥ 50-D

DFS 遞迴搜尋

圖節點 ≤ 100，DFS 完全足夠。用 visited 陣列避免重複搜尋。

完整 C 代碼

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

#define MAXN 105

int N, D;
int x[MAXN], y[MAXN];
bool vis[MAXN];

bool can_first_jump(int i) {
    // 島半徑 7.5 → 距原點 ≤ D + 7.5
    // 為避免浮點，乘 2：距原點 ≤ 2D + 15
    int dist2 = x[i]*x[i] + y[i]*y[i];
    int limit = (2*D + 15);
    return dist2 <= limit * limit;
}

bool can_escape(int i) {
    return (abs(x[i]) >= 50 - D) || (abs(y[i]) >= 50 - D);
}

bool can_jump(int i, int j) {
    int dx = x[i] - x[j];
    int dy = y[i] - y[j];
    return dx*dx + dy*dy <= D*D;
}

bool dfs(int u) {
    vis[u] = true;
    if (can_escape(u)) return true;
    for (int v = 0; v < N; ++v) {
        if (!vis[v] && can_jump(u, v)) {
            if (dfs(v)) return true;
        }
    }
    return false;
}

int main(void) {
    scanf("%d %d", &N, &D);
    for (int i = 0; i < N; ++i) scanf("%d %d", &x[i], &y[i]);

    bool ok = false;
    for (int i = 0; i < N && !ok; ++i) {
        if (!vis[i] && can_first_jump(i))
            ok = dfs(i);
    }
    puts(ok ? "Yes" : "No");
    return 0;
}

整數運算避免浮點誤差

• 所有距離比較改用**平方距離**，完全整數運算
• 第一跳半徑 7.5 處理：將不等式兩邊同乘 2，dist ≤ D + 7.5 → 2·dist ≤ 2D + 15，平方後比較
• abs() 需 <stdlib.h>，注意整數版本

樣例驗證

輸入 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
輸出: Yes

輸入 2:
4 13
-12 12
12 12
-12 -12
12 -12
輸出: No

複雜度與優化

• 時間：O(N²)，N ≤ 100 極快
• 空間：O(N)
• 可改用 BFS 避免遞迴棧溢位 (此處深度 ≤ 100 安全)