問題描述

20×20 棋盤，0=空地，1=石頭，2=起點，3=終點。冰壺從起點出發，選一方向滑動，遇石頭停在石頭前一格並移除該石頭，遇終點停下結束。最多 10 步，求能否到達終點，輸出最少步數。

狀態與搜索

• 狀態：位置 (r,c)、棋盤石頭分布、步數。
• 操作：靜止時可選 4 方向滑動；滑動中不可改向，直到撞石頭/終點/邊界。
• 限制：步數 ≤ 10，棋盤 20×20，石頭 ≤ 10，DFS 可行。

DFS 設計

void dfs(int r, int c, int step, bool moving, int dir, bool remove_flag) {
    if (step > 10) return;
    if (board[r][c] == 3) { ans = min(ans, step); return; }
    
    if (remove_flag) { // 上一步撞石頭，恢復石頭用於回溯
        // 根據 dir 恢復 board[nr][nc] = 1
    }
    
    if (!moving) { // 靜止，嘗試 4 方向
        for (int d=0; d<4; ++d) {
            int nr=r+dr[d], nc=c+dc[d];
            if (in_board(nr,nc) && (board[nr][nc]==0 || board[nr][nc]==3))
                dfs(nr, nc, step+1, true, d, false);
        }
    } else { // 滑動中
        int nr=r+dr[dir], nc=c+dc[dir];
        if (!in_board(nr,nc)) return; // 出界停止
        if (board[nr][nc] == 0) 
            dfs(nr, nc, step, true, dir, false); // 繼續滑動，步數不增
        else if (board[nr][nc] == 1) { // 撞石頭
            board[nr][nc] = 0; // 移除
            dfs(r, c, step+1, false, dir, true); // 停在當前格，步數+1
        }
        else if (board[nr][nc] == 3) // 到達終點
            dfs(nr, nc, step, false, dir, false);
    }
    
    if (remove_flag) { // 回溯恢復石頭
        // 根據 dir 恢復 board[nr][nc] = 1
    }
}

關鍵細節

1. 步數計數：只有「發起滑動」和「撞石頭停下」算一步。滑動過程中不計步。
2. 石頭移除與回溯：撞石頭前移除，遞歸返回後恢復，保證棋盤狀態正確。
3. 終點處理：滑入終點即成功，不再滑動。
4. 剪枝：step > 10 直接返回；找到解更新全局最小值。

完整代碼結構

#include <iostream>
using namespace std;

int w, h, board[22][22], ans;
int dr[4] = {-1,0,1,0}, dc[4] = {0,-1,0,1}; // N,W,S,E

void dfs(int r, int c, int step, bool moving, int dir, bool hit) {
    if (step > 10) return;
    if (board[r][c] == 3) { ans = min(ans, step); return; }
    
    if (hit) { // 恢復上一步移除的石頭
        int pr = r - dr[dir], pc = c - dc[dir];
        board[pr][pc] = 1;
    }
    
    if (!moving) {
        for (int d=0; d<4; ++d) {
            int nr=r+dr[d], nc=c+dc[d];
            if (nr>=1 && nr<=h && nc>=1 && nc<=w && (board[nr][nc]==0 || board[nr][nc]==3))
                dfs(nr, nc, step+1, true, d, false);
        }
    } else {
        int nr=r+dr[dir], nc=c+dc[dir];
        if (nr<1 || nr>h || nc<1 || nc>w) return;
        if (board[nr][nc] == 0)
            dfs(nr, nc, step, true, dir, false);
        else if (board[nr][nc] == 1) {
            board[nr][nc] = 0;
            dfs(r, c, step+1, false, dir, true);
        }
        else if (board[nr][nc] == 3)
            dfs(nr, nc, step, false, dir, false);
    }
    
    if (hit) { // 回溯再次移除（其實上方已恢復，這裡需再次移除供下一個方向？需仔細設計）
        // 更清晰：在撞石頭分支內部處理移除/恢復，避免全局 hit 標記
    }
}

int main() {
    while (cin>>w>>h, w||h) {
        ans = 11;
        int sr, sc;
        for (int i=1;i<=h;++i)
            for (int j=1;j<=w;++j) {
                cin>>board[i][j];
                if (board[i][j]==2) { sr=i; sc=j; board[i][j]=0; }
            }
        dfs(sr, sc, 0, false, 0, false);
        if (ans <= 10) cout << ans << '\n';
        else cout << -1 << '\n';
    }
    return 0;
}

優化版回溯邏輯

在「撞石頭」分支：

else if (board[nr][nc] == 1) {
    board[nr][nc] = 0;           // 移除
    dfs(r, c, step+1, false, dir, false);
    board[nr][nc] = 1;           // 回溯恢復
}

無需額外 hit 參數，代碼更清晰。

複雜度

• 每步最多 4 方向，深度 ≤ 10，狀態數 ≤ 4^10 ≈ 100萬，實際因石頭阻擋、邊界、剪枝大幅減少。
• 時間：< 0.1s。

總結

POJ 3009 是 DFS 模擬題，關鍵在於正確建模「滑動狀態」與「步數計數」，並在撞石頭時正確處理棋盤修改與回溯。將「發起滑動」和「撞石頭停下」計為一步，滑動過程不計步，是理解題意的關鍵。代碼中用 moving 區分靜止/滑動狀態，遞歸參數傳遣方向，回溯時原地恢復石頭，結構清晰易懂。