HDU 5040 另解：三維訪問數組剪枝優化

HDU 5040 另解：三維訪問數組剪枝優化

同 HDU 5040，採用 vis[x][y][time%4] 精確記錄「在時刻模 4 為 t 時到達 (x,y)」，避免同模態重複搜索。比單純 best[x][y] 更精確，防止「同位置不同時刻模態」互相干擾。

狀態擴展

struct State {
    int x, y, time;
    bool operator<(State o) const { return time > o.time; }
};

int vis[505][505][4]; // 0/1 標記
int light[505][505][4]; // 預處理：該時刻模態下是否被照

// BFS
priority_queue<State> pq;
pq.push({sx, sy, 0});
vis[sx][sy][0] = 1;

while (!pq.empty()) {
    auto cur = pq.top(); pq.pop();
    if (cur.x == tx && cur.y == ty) return cur.time;
    
    // 原地等待 1 秒（換模態）
    State nxt = cur; nxt.time++;
    if (!vis[nxt.x][nxt.y][nxt.time%4]) {
        vis[nxt.x][nxt.y][nxt.time%4] = 1;
        pq.push(nxt);
    }
    
    // 四方向移動
    for (dir) {
        nx, ny = cur.x+dx, cur.y+dy;
        if (invalid) continue;
        
        if (light[nx][ny][cur.time%4] || light[cur.x][cur.y][cur.time%4]) {
            nxt.time = cur.time + 3; // 鑽箱
        } else {
            nxt.time = cur.time + 1; // 正常
        }
        nxt.x = nx; nxt.y = ny;
        if (!vis[nx][ny][nxt.time%4]) {
            vis[nx][ny][nxt.time%4] = 1;
            pq.push(nxt);
        }
    }
}

光照預處理

遍歷地圖，對每個攝像頭，根據初始朝向，計算其在 t=0,1,2,3 照射的格子（含自身、前方 1 格），標記 light[x][y][t]=1。

優勢

• 狀態空間精確：N×N×4，N=500 約 100 萬狀態
• 無需運行時判斷光照，O(1) 查表
• 自然支持原地等待換相位
• 代碼簡潔，邏輯清晰

注意

終點 'T' 視為 '.' 處理（可正常進入），起點 'M' 同理。輸出 Case #x: y，不可達輸出 -1。