ZOJ 3823 Excavator Contest：構造題讓挖掘機遍歷 N×N 格子並達到最小轉彎數

ZOJ 3823 Excavator Contest：構造題讓挖掘機遍歷 N×N 格子並達到最小轉彎數

在 N×N 網格中，挖掘機需走遍所有格子恰好一次（哈密頓路徑），起終點均在邊界，且轉彎次數 ≥ N(N-1)-1。輸出任意合法路徑編碼（1~N^2 的排列）。

構造核心觀察

• 網格圖哈密頓路徑存在性：N 為奇數時從一角出發蛇形遍歷即可；N 為偶數時需精心設計避免死循環；
• 轉彎數下界 N(N-1)-1 接近理論最大值（完全蛇形約 N^2），故路徑必須極其「彎曲」；
• 起終點在邊界 ⇒ 進入內部後必須留出退路。

分類構造策略

N 為奇數

從 (N, N) 起點，採用「外圍繞圈 + 內部遞歸」模式，保證每層繞一圈後進入下一層，轉彎數自然達標。具體路徑見代碼 moveup/moveleft/movedown 協同。

N 為偶數

根據 N/2 mod 4 分四類，起終點位置各異：

每類對應不同的「剝洋蔥」遍歷順序，代碼中通過 dir_up/down/left 查表實現。

關鍵遞歸框架

void solve(int n, int sx, int sy, int ex, int ey, int flag) {
    if (n <= 1) { if (n==1) g[sx][sy] = L; return; }
    if (n & 1) {                    // 奇數層
        if ((n/2) & 1) {
            if (flag) { moveup(n, sx, sy, L, 1); moveleft(n, ex, ey, R, -1); }
            else { moveup(n, ex, ey, R, -1); moveleft(n, sx, sy, L, 1); }
            solve(n-2, sx, sy, ex, ey, flag);
        } else {
            if (flag) movedown(n, ex, ey, R, -1);
            else movedown(n, sx, sy, L, 1);
            solve(n-2, sx, sy, ex, ey, flag^1);
        }
    } else {                        // 偶數層
        if ((n/2) & 1) {
            if (flag) movedown(n, ex, ey, R, -1);
            else movedown(n, sx, sy, L, 1);
            solve(n-2, sx, sy, ex, ey, flag^1);
        } else {
            if (flag) { moveup(n, sx, sy, L, 1); moveleft(n, ex, ey, R, -1); }
            else { moveup(n, ex, ey, R, -1); moveleft(n, sx, sy, L, 1); }
            solve(n-2, sx, sy, ex, ey, flag);
        }
    }
}

其中 L 從 1 遞增，R 從 N^2 遞減，雙向填充保證無衝突。

移動原語 jump

inline void jump(int n, int& x, int& y, int& mv, int len, const int d[4]) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < 4; ++j) {
            g[x][y] = mv;
            mv += len;
            x += dir[d[j]][0]; y += dir[d[j]][1];
        }
}

dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}} 對應上下左右。dir_up/down/left 編碼了每層的具體轉向序列。

複雜度與驗證

• 時間 O(N^2)，單次填充每個格子一次；
• 空間 O(N^2) 存網格；
• 輸出檢查：所有 1~N^2 恰好出現一次，相鄰數字曼哈頓距離為 1，起終點在邊界，轉彎數 ≥ N(N-1)-1。

心得體會

這是我做過最惡心的構造題。關鍵在於將奇/偶、層數模 4、flag 翻轉等條件全部枚舉清楚，構建查表驅動的移動原語，避免手寫分支漏情況。調試時建議小 N 打印網格人工驗證路徑連通性。

完整 AC 代碼約 150 行，屬於「寫一次用一輩子」的構造模板，掌握其「分層剝洋蔥 + 雙向填充 + 查表轉向」思想，可應對多類網格哈密頓路徑構造變種。