HDU 1010 Tempter of the Bone：DFS + 奇偶剪枝

題目大意

N×M 迷宮，'S' 起點，'D' 終點，'X' 障礙，'.' 可通行。要求**恰好**在 T 步到達終點（非 ≤ T），每步只能上下左右移動，不可重複訪問同一格。判斷是否可能。

核心剪枝：曼哈頓距離奇偶性

設最短路徑長 `dist = |Sx-Dx| + |Sy-Dy|`。

• 任何繞路都會增加**偶數**步數（進出繞行各一次）
• 因此所有可行路徑長度與 `dist` 奇偶性相同
• 若 `(T - dist) % 2 != 0`，直接判定不可能

DFS 實現

int n, m, T;
char maze[10][10];
int sx, sy, dx, dy;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

bool dfs(int x, int y, int step) {
    if (x == dx && y == dy) return step == T;
    if (step >= T) return false;
    
    // 奇偶剪枝（可選，DFS 本身也會自然剪枝）
    int min_need = abs(x-dx) + abs(y-dy);
    if ((T - step - min_need) % 2 != 0) return false;
    if (min_need > T - step) return false; // 剩餘步數不足
    
    for (int d = 0; d < 4; ++d) {
        int nx = x + dir[d][0], ny = y + dir[d][1];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (maze[nx][ny] == 'X') continue;
        
        maze[nx][ny] = 'X'; // 標記已訪問
        if (dfs(nx, ny, step + 1)) return true;
        maze[nx][ny] = '.'; // 回溯恢復
    }
    return false;
}

int main() {
    while (cin >> n >> m >> T, n) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                cin >> maze[i][j];
                if (maze[i][j] == 'S') sx=i, sy=j;
                if (maze[i][j] == 'D') dx=i, dy=j;
            }
        int dist = abs(sx-dx) + abs(sy-dy);
        if (dist > T || (T - dist) % 2) {
            cout << "NO\n";
        } else {
            maze[sx][sy] = 'X';
            cout << (dfs(sx, sy, 0) ? "YES" : "NO") << '\n';
        }
    }
}

大神優化版（無額外剪枝也能 AC）

bool dfs_fast(int x, int y, int t) {
    if (t == 1) { // 剩 1 步時檢查四鄰域是否有 D
        return maze[x-1][y]=='D' || maze[x+1][y]=='D' 
            || maze[x][y-1]=='D' || maze[x][y+1]=='D';
    }
    maze[x][y] = 'X';
    if (maze[x-1][y]=='.' && dfs_fast(x-1,y,t-1)) return true;
    if (maze[x+1][y]=='.' && dfs_fast(x+1,y,t-1)) return true;
    if (maze[x][y-1]=='.' && dfs_fast(x,y-1,t-1)) return true;
    if (maze[x][y+1]=='.' && dfs_fast(x,y+1,t-1)) return true;
    maze[x][y] = '.';
    return false;
}

關鍵點總結

複雜度

最壞 O(4^T)，但剪枝後實際極快，N,M ≤ 7, T 適中時毫秒級通過。