POJ Collecting Beepers：TSP 曼哈頓距離 DFS 暴力搜索

問題描述

20×20 網格，起點 1 個，最多 10 個 beeper。機器人只能上下左右移動（曼哈頓距離）。求從起點出發，收集所有 beeper 並返回起點的最短路徑長度。

解法：全排列 + 剪枝 DFS

• 預計算所有點對距離（曼哈頓）。
• DFS 狀態：dfs(cur, visitedMask, dist)。
• 當 visitedMask == all，更新答案 ans = min(ans, dist + dist[cur][start])。
• 剪枝：dist >= ans 直接返回。

參考代碼片段

int dist[12][12];
int ans, allMask;

void dfs(int u, int mask, int d) {
    if (d >= ans) return;
    if (mask == allMask) {
        ans = min(ans, d + dist[u][0]);
        return;
    }
    for (int v = 1; v <= n; v++)
        if (!(mask & (1<

複雜度

狀態數：n ≤ 10，最多 10! ≈ 3.6M，剪枝後極快。
時間：O(n!) 最壞，實測毫秒級。


總結
小規模 TSP 經典暴力解。曼哈頓距離滿足三角不等式，但此處直接全排列枚舉順序即可。注意起點編號為 0，beeper 1~n，allMask 包含起點位。輸出格式固定。