POJ 3009：Curling 2.0——DFS 搜索最少移動次數

題目背景

冰面棋盤遊戲：石頭從起點 S 出發，沿直線滑動直到撞到障礙（1）或出界（失敗）或到達終點 G（成功）。撞到障礙時停在障礙前一格，障礙消失，可重新選擇方向繼續。最多 10 次移動，求最少移動次數到達 G。

輸入格式

• 多組數據，每組先給 w h（寬、高 ≤ 20）
• 棋盤：0 空地、1 障礙、2 起點、3 終點
• 0 0 結束

DFS 回溯算法

1. 從起點開始，嘗試四個方向
2. 沿方向滑動直到撞障礙/出界/到達終點
3. 撞障礙：移除障礙，遞歸搜索下一步，回溯時恢復障礙
4. 剪枝：步數 ≥ 10 或 ≥ 當前最優解 → 返回
5. 記錄全局最小步數

C++ 實現（關鍵片段）

int vis[25][25], w, h, sx, sy, gx, gy, minStep = 1e9;
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

void dfs(int x, int y, int step) {
    if (step >= 10 || step >= minStep) return;
    for (int d = 0; d < 4; ++d) {
        int nx = x + dx[d], ny = y + dy[d];
        if (vis[nx][ny]) continue; // 相鄰即障礙/邊界，無法移動
        // 滑動
        while (!vis[nx][ny]) {
            nx += dx[d]; ny += dy[d];
            if (nx == gx && ny == gy) { minStep = min(minStep, step+1); return; }
            if (nx < 0 || nx >= h || ny < 0 || ny >= w) break; // 出界
        }
        // 撞到障礙 (nx,ny) 是障礙，石頭停在 (nx-dx, ny-dy)
        if (nx >= 0 && nx < h && ny >= 0 && ny < w && step+1 < 10) {
            vis[nx][ny] = 0;           // 移除障礙
            dfs(nx-dx[d], ny-dy[d], step+1);
            vis[nx][ny] = 1;           // 回溯恢復
        }
    }
}

注意事項

• 數組下標：輸入 w h 但存儲常用 [h][w]
• 起點/終點讀入後標記為 0（空地）
• G++ 編譯通過，C++ 編譯可能 RE（栈大小差異）

複雜度

• 狀態數 ≤ 4¹⁰ = 1,048,576，實際剪枝後極快
• 時間：O(4^深度)，深度 ≤ 10