POJ 3009 Curling 2.0：DFS 回溯求冰壺最少投擲次數

POJ 3009 Curling 2.0：DFS 回溯求冰壺最少投擲次數

問題描述

w×h 棋盤（w≤20, h≤20），0 空地，1 障礙，2 起點，3 終點。冰壺從起點出發，每次選一個方向投擲，直線滑動直到：

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

投擲方向相鄰格不能是障礙。最多 10 次投擲，求最少次數，失敗輸出 -1。

DFS 回溯搜索

• 狀態：當前位置 (x,y)、投擲次數 cnt
• 剪枝：cnt > 10 返回；cnt ≥ 當前最優解返回
• 四方向嘗試：若相鄰格無障礙，模擬滑動
• 滑動模擬：循環前進直到撞障礙/出界/到終點
• 撞障礙：障礙置 0，遞歸搜索，回溯恢復障礙
• 到終點：更新最優解

完整 AC 代碼

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 25, INF = 0x3f3f3f3f;
int w, h, sx, sy, ex, ey, minn;
int mp[maxn][maxn];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
bool fail;

bool inBoard(int x, int y) { return x>=0 && x=0 && y 10) return;
    for (int d = 0; d < 4; d++) {
        int nx = x + dir[d][0], ny = y + dir[d][1];
        if (!inBoard(nx, ny) || mp[nx][ny] == 1) continue; // 相鄰是障礙或出界，不能投
        // 模擬滑動
        while (inBoard(nx, ny) && mp[nx][ny] != 1) {
            if (mp[nx][ny] == 3) { // 到達終點
                if (cnt + 1 < minn) { minn = cnt + 1; fail = false; }
                return;
            }
            nx += dir[d][0]; ny += dir[d][1];
        }
        if (!inBoard(nx, ny)) continue; // 滑出界
        // 撞到障礙：停在障礙前一格，障礙消失
        mp[nx][ny] = 0;
        dfs(nx - dir[d][0], ny - dir[d][1], cnt + 1);
        mp[nx][ny] = 1; // 回溯恢復
    }
}

int main() {
    while (scanf("%d%d", &w, &h), w || h) {
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++) {
                scanf("%d", &mp[i][j]);
                if (mp[i][j] == 2) { sx = i; sy = j; }
                else if (mp[i][j] == 3) { ex = i; ey = j; }
            }
        fail = true; minn = INF;
        dfs(sx, sy, 0);
        if (fail || minn > 10) printf("-1\n");
        else printf("%d\n", minn);
    }
    return 0;
}

關鍵細節

1. 投擲前檢查相鄰格：必須非障礙且在板內
2. 滑動循環條件：在板內且非障礙
3. 撞障礙後位置：障礙前一格
4. 障礙消失需回溯恢復
5. 全局變量 fail 標記是否有解