POJ 2907 Collecting Beepers：DFS 回溯解決 TSP 變體

題目大意

機器人 Karel 在 20×20 網格中，從起點出發，需收集 ≤10 個信標（Beeper）並返回起點。移動代價為曼哈頓距離。求最短總路徑長度。

問題建模

這是一個旅行商問題 (TSP) 的小規模實例：

• 節點：起點 + 所有信標位置，共 n+1 ≤ 11 個點。
• 邊權：任意兩點間的曼哈頓距離 |x1-x2| + |y1-y2|。
• 目標：從起點出發，拜訪所有信標恰好一次，返回起點，總距離最小。

DFS + 剪枝求解

由於 n ≤ 10，全排列狀態數 10! = 3.6e6，配合剪枝極快。狀態：

• dfs(cur_x, cur_y, visited_count, current_length)
• visited[i] 標記第 i 個信標是否已收集。

剪枝策略

1. 當前長度 ≥ 最佳答案：直接返回。
2. 啟發式下界：可加入剩餘未訪問點的最小生成樹或最近鄰下界，但本題純 DFS + 當前長度剪枝已足夠。

核心代碼實現

struct Point { int x, y; };
Point pts[15];  // 0: 起點, 1..n: 信標
int n, best;
bool vis[15];

int dist(int i, int j) {
    return abs(pts[i].x - pts[j].x) + abs(pts[i].y - pts[j].y);
}

void dfs(int u, int cnt, int len) {
    if (len >= best) return;           // 剪枝
    if (cnt == n) {                    // 全部收集完，回起點
        best = min(best, len + dist(u, 0));
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (!vis[v]) {
            vis[v] = true;
            dfs(v, cnt + 1, len + dist(u, v));
            vis[v] = false;
        }
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int w, h; scanf("%d%d", &w, &h);
        scanf("%d%d", &pts[0].x, &pts[0].y);
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d%d", &pts[i].x, &pts[i].y);
        best = INT_MAX;
        memset(vis, 0, sizeof(vis));
        dfs(0, 0, 0);
        printf("The shortest path has length %d\n", best);
    }
}

優化方向（可選）

• DP + 狀態壓縮：dp[mask][i] 表示已訪問集合 mask 且當前在點 i 的最短距離。狀態數 2^10 × 10 = 10240，轉移 O(n)，極快且無需剪枝技巧。
• 最近鄰排序：在 DFS 中優先嘗試距離最近的未訪問點，更快找到優解，增強剪枝效果。

複雜度

DFS 最壞 O(n!)，但剪枝後實際極快；DP 狀態壓縮 O(n² 2ⁿ) 穩定高效。本題 n ≤ 10 兩種做法均可 AC。

注意事項

• 起點也可能有信標？題目說信標位置各不相同，但未說明是否與起點重疊。代碼中將起點單獨存為 pts[0]，信標從 1 開始，自動處理重疊情況（距離為 0）。
• 輸出格式嚴格：「The shortest path has length X」。
• 多測資料循環讀取直到 EOF。