您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 1180 詭異的樓梯：時間維度狀態 BFS 最短路

編輯：關於C++

問題描述

M×N 地圖 (≤20×20)。『.』走廊、『*』障礙、『|』豎直梯、『-』水平梯、『S』起點、『T』終點。梯子每分鐘翻轉一次。哈利每分鐘移動一格（上下左右），上梯子經過對面也需 1 分鐘，不在梯停留。梯子在哈利移動後翻轉。求最短時間。

核心建模：狀態 = (x, y, time%2)

梯子狀態只與時間奇偶性有關：

偶數時刻 (t%2==0)：梯子保持初始狀態 (| 豎直, - 水平)
奇數時刻 (t%2==1)：梯子翻轉 (| 變水平, - 變豎直)

狀態空間：20×20×2 = 800，極小，直接 BFS。

移動規則詳細

目標格為 `.` `S` `T`：直接移動，耗時 1
目標格為梯子：
- 當前梯子方向允許通過 (豎直梯上下移動、水平梯左右移動) → 上梯經過對面，耗時 1，落地於梯子另一側
- 方向不允許 → 視為普通通道，耗時 1 移動到梯子格

完整代碼 (Dijkstra / 優先隊列 BFS)


#include 
#include 
#include 
using namespace std;

struct Node {
    int x, y, t;
    bool operator<(const Node& o) const { return t > o.t; }  // 小頂堆
};

char map[25][25];
int dist[25][25][2];
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
int M, N, sx, sy, tx, ty;

bool isLadder(char c) { return c == '|' || c == '-'; }
bool isVertical(char c, int parity) {  // parity=0 偶數時刻
    if (c == '|') return parity == 0;
    if (c == '-') return parity == 1;
    return false;
}

int main() {
    while (scanf("%d%d", &M, &N) == 2) {
        for (int i = 0; i < M; ++i) {
            scanf("%s", map[i]);
            for (int j = 0; j < N; ++j) {
                if (map[i][j] == 'S') { sx = i; sy = j; }
                if (map[i][j] == 'T') { tx = i; ty = j; }
            }
        }
        memset(dist, 0x3f, sizeof(dist));
        priority_queue pq;
        dist[sx][sy][0] = 0;
        pq.push({sx, sy, 0});
        
        while (!pq.empty()) {
            Node u = pq.top(); pq.pop();
            if (u.t > dist[u.x][u.y][u.t % 2]) continue;
            if (u.x == tx && u.y == ty) { printf("%d\n", u.t); break; }
            
            for (int d = 0; d < 4; ++d) {
                int nx = u.x + dx[d], ny = u.y + dy[d];
                if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
                char target = map[nx][ny];
                if (target == '*') continue;
                
                int nt = u.t + 1;
                int npar = nt % 2;
                
                if (isLadder(target)) {
                    bool vertical = isVertical(target, u.t % 2);  // 移動前梯子狀態
                    bool movingVert = (dx[d] != 0);  // 上下移動
                    
                    if (vertical == movingVert) {  // 方向匹配，上梯經過
                        int nnx = nx + dx[d], nny = ny + dy[d];
                        if (nnx >= 0 && nnx < M && nny >= 0 && nny < N && map[nnx][nny] != '*') {
                            if (nt < dist[nnx][nny][npar]) {
                                dist[nnx][nny][npar] = nt;
                                pq.push({nnx, nny, nt});
                            }
                        }
                    } else {  // 方向不匹配，當作普通格
                        if (nt < dist[nx][ny][npar]) {
                            dist[nx][ny][npar] = nt;
                            pq.push({nx, ny, nt});
                        }
                    }
                } else {  // 普通格
                    if (nt < dist[nx][ny][npar]) {
                        dist[nx][ny][npar] = nt;
                        pq.push({nx, ny, nt});
                    }
                }
            }
        }
    }
    return 0;
}