POJ 3009 Curling 2.0：DFS 限步搜尋冰壺最少投擲次數

題目

W×H (≤20) 冰面，2 起點，3 終點，1 障礙塊，0 空地。石塊投擲後沿直線滑動直到：

• 撞到障礙 → 停在障礙前一格，障礙消失。
• 滑出邊界 → 失敗。
• 到達終點 → 成功。

最多投擲 10 次，求最少次數，失敗輸出 -1。

解法：帶剪枝的 DFS

1. 從起點嘗試 4 個方向投擲。
2. 模擬滑動：逐步前進，遇障礙/終點/邊界處理。
3. 撞障礙時：暫時移除障礙，遞歸搜尋下一步（步數+1），回溯恢復障礙。
4. 剪枝：step >= 10 或 step >= best 直接返回。

C++ 代碼

#include 
using namespace std;
const int MAX = 20;
int grid[MAX][MAX], W, H, best;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {-1,0,1,0};

void dfs(int x, int y, int step) {
    if (step >= 10 || step >= best) return;
    for (int d = 0; d < 4; ++d) {
        int nx = x, ny = y;
        // 先檢查緊鄰格是否為障礙（不可直接投向障礙）
        if (x+dx[d] < 0 || x+dx[d] >= H || y+dy[d] < 0 || y+dy[d] >= W) continue;
        if (grid[x+dx[d]][y+dy[d]] == 1) continue;
        // 滑動
        while (true) {
            nx += dx[d]; ny += dy[d];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) break; // 出界
            if (grid[nx][ny] == 3) { best = min(best, step+1); break; } // 到達終點
            if (grid[nx][ny] == 1) { // 撞障礙
                int bx = nx - dx[d], by = ny - dy[d]; // 停在障礙前
                if (bx != x || by != y) { // 確實移動了
                    grid[nx][ny] = 0; // 移除障礙
                    dfs(bx, by, step+1);
                    grid[nx][ny] = 1; // 回溯
                }
                break;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> W >> H, W) {
        int sx=0, sy=0;
        for (int i = 0; i < H; ++i)
            for (int j = 0; j < W; ++j) {
                cin >> grid[i][j];
                if (grid[i][j] == 2) { sx = i; sy = j; }
            }
        grid[sx][sy] = 0; // 起點視為空地
        best = 11;
        dfs(sx, sy, 0);
        if (best > 10) best = -1;
        cout << best << "\n";
    }
    return 0;
}

關鍵細節

• 投擲方向若緊鄰即為障礙，規則禁止該方向投擲。
• 撞障礙後石塊停在障礙**前一格**，障礙消失。
• 步數限制 10 為硬剪枝，配合 best 優化。