UVA 503：三維展開為二維平面求最短直線距離

題目挑戰

經典的「螞蟻爬盒子」問題變體：長方體表面上兩點間的最短路徑。將三維展開為二維平面，求直線距離最小值。WA 一天才發現：除考慮經過 0、1 個面外，必須考慮經過兩個面到達的情況。

核心幾何洞察

長方體尺寸 L×W×H，起點 (x1,y1,z1)、終點 (x2,y2,z2)。終點若在某個面上（如 x2=0 或 x2=L 等），展開方式不同。代碼通過 solve 函數枚舉所有合法展開方式，計算二維平面歐幾里得距離平方，取最小值。主函數再對稱交換起終點、旋轉維度，確保覆蓋所有拓撲可能。

關鍵代碼片段

ll solve(int L, int W, int H, int x1, int y1, int z1, int x2, int y2, int z2) {
    ll ans = inf;
    if (x2 == 0) {
        ans = min(ans, Dis(Point(x1, y1), Point(-z2, y2)));
        ans = min(ans, Dis(Point(x1, y1), Point(y2-W, z2+W)));
        ans = min(ans, Dis(Point(x1, y1), Point(-y2, -z2)));
        ans = min(ans, Dis(Point(x1, y1), Point(z2-H, 2*W+H-y2)));
        ans = min(ans, Dis(Point(x1, y1), Point(z2-H, -(H+y2))));
    }
    // ... x2==L, z2==0, z2==H 同理枚舉
    return ans;
}

int main() {
    int L,W,H,x1,y1,z1,x2,y2,z2;
    while (scanf("%d%d%d%d%d%d%d%d%d", &L,&W,&H,&x1,&y1,&z1,&x2,&y2,&z2) == 9) {
        ll ans = inf;
        for (int i = 0; i < 2; ++i) {
            if (x1 == 0) {
                ans = min(ans, solve(W, H, L, y1, z1, x1, y2, z2, x2));
                ans = min(ans, solve(H, W, L, z1, y1, x1, z2, y2, x2));
            } else if (x1 == L) { ... }
            // ... y1==0, y1==W, z1==0, z1==H 分支
            swap(x1,x2); swap(y1,y2); swap(z1,z2); // 對稱交換
        }
        printf("%lld\n", ans);
    }
}

測試數據生成器

文末附帶隨機數據生成代碼，可用於驗證解法正確性。