HDU 1010 Tempter of the Bone - DFS 剪枝尋路

問題描述

迷宮 N×M (N,M<7)，起點 S，終點 D，牆壁 X。每秒移動一格（上下左右），進入格子後下一秒沉陷（不可再次進入）。必須在第 T 秒恰好到達 D。判斷是否可行。

DFS + 關鍵剪枝

狀態：(x, y, time)。剪枝條件：

1. time > T 超時。
2. 曼哈頓距離 dist = |ex-x| + |ey-y|。剩餘步數 rem = T - time。
   • 若 rem < dist 來不及。
   • 若 (rem - dist) % 2 != 0 多出的步數無法消耗（來回走需偶數步）。
3. 到達 D 但 time != T 失敗。

代碼實現（C++）

#include 
#include 
#include 
using namespace std;

const int MAXN = 10;
char maze[MAXN][MAXN];
bool vis[MAXN][MAXN];
int N, M, T, sx, sy, ex, ey;
int dx[4] = {0,0,-1,1}, dy[4] = {1,-1,0,0};
bool ok;

void dfs(int x, int y, int t) {
    int dist = abs(ex-x) + abs(ey-y);
    int rem = T - t;
    if (ok || t > T || rem < dist || (rem - dist) % 2) return;
    if (t == T && x == ex && y == ey) { ok = true; return; }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx<0 || nx>=N || ny<0 || ny>=M) continue;
        if (maze[nx][ny] == 'X' || vis[nx][ny]) continue;
        vis[nx][ny] = true;
        dfs(nx, ny, t+1);
        vis[nx][ny] = false;
    }
}

int main() {
    while (cin >> N >> M >> T) {
        if (N==0 && M==0 && T==0) break;
        ok = false;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < N; i++) {
            cin >> maze[i];
            for (int j = 0; j < M; j++) {
                if (maze[i][j] == 'S') { sx=i; sy=j; }
                if (maze[i][j] == 'D') { ex=i; ey=j; }
            }
        }
        vis[sx][sy] = true;
        dfs(sx, sy, 0);
        cout << (ok ? "YES" : "NO") << endl;
    }
    return 0;
}

複雜度分析

狀態數上界 7×7×50 = 2450，剪枝極其有效，瞬間通過。