HDU 1180 詭異的樓梯：BFS + 優先隊列處理動態障礙

題目情境與難點

M, N ≤ 20 地圖，字元含義：
* 牆、. 走廊、S 起點、T 終點、| 初始豎向樓梯、- 初始橫向樓梯。
樓梯每分鐘翻轉一次（豎↔橫）。Harry 每分鐘移動一格（上下左右），進入樓梯格並穿越到對面只消耗 1 分鐘，且樓梯在 Harry 移動完畢後才翻轉。求最短時間。

狀態空間與 Dijkstra（優先隊列 BFS）

狀態：(x, y, step)。因樓梯狀態由 step % 2 決定，無需額外維度。
使用 priority_queue 按 step 從小到大展開（等價於 Dijkstra，邊權均為 1 或 2）。
dist[x][y] 記錄到達 (x,y) 的最小步數，允許「以更小 step 重複訪問同一格」。

樓梯通行邏輯：核心判斷函數

設當前步數 t，當前格 (x, y)，目標相鄰格 (nx, ny)：

• 若 (nx, ny) 非樓梯：正常移動，step+1。
• 若為 |（初始豎向）：
  • 豎向時（t%2==0）允許上下通行（nx != x），橫向時（t%2==1）允許左右通行（ny != y）。
  • 方向不匹配時可原地等待 1 分鐘（step+1），再嘗試通行（再 +1，共 +2）。
  • 通行成功後，Harry 直接出現在樓梯對面格子（再加一次 dx, dy）。
• -（初始橫向）邏輯對稱：t%2==1 橫向通行，t%2==0 豎向通行。

判斷函數 judge(node) 精簡版

bool judge(node u) {
    if (u.x<0 || u.x>=n || u.y<0 || u.y>=m) return false;
    if (map[u.x][u.y] == '*') return false;
    if (dist[u.x][u.y] && u.step >= dist[u.x][u.y]) return false; // 已有更優路徑
    return true;
}

完整 BFS 流程

push (Sx, Sy, 0)
while pq not empty:
    cur = pq.top(); pq.pop()
    for 4 directions:
        nxt = cur + dir; nxt.step = cur.step + 1
        if !judge(nxt) continue
        if map[nxt] is stair:
            // 檢查方向匹配，不匹配則 nxt.step++ 等待
            // 通行後 nxt 再加一次 dir 落在對面
            if !judge(nxt) continue
        if map[nxt] == 'T': return nxt.step
        dist[nxt] = nxt.step
        pq.push(nxt)

關鍵細節總結

• 優先隊列保證首次到達 T 即最短路（因邊權非負）。
• 不使用 vis[][] 永久標記，改用 dist[][] 記錄最小步數，允許「更早到達」時重入。
• 樓梯符號同時處理 | 和 -，原碼曾因漏掉 - 多次 WA。
• 等待邏輯：方向錯時 step++ 原地等待，不移動座標，下一輪迴圈會重新判斷同一樓梯格（此時方向已翻轉）。

總結

本題將「時間依賴的動態障礙」建模為「步數模 2 決定樓梯朝向」，配合 Dijkstra（優先隊列 BFS）在狀態圖上搜尋。核心難點在於正確實作「進入樓梯→檢查方向→可選等待→穿越對面」的多步原子操作，並以 dist[][] 取代傳統 vis[][] 以支持「更優路徑覆蓋」。