ZOJ 3103 Cliff Climbing：SPFA 求最短攀爬時間

問題描述

懸崖 h×w 格子（h≤60, w≤30）。起點：底行 'S'；終點：頂行 'T'。格子：'X' 不可踏，'1'~'9' 踏上需對應時間，'S'/'T' 耗時 0。雙腳交替移動：左腳在 (lx,ly)，右腳在 (rx,ry)，滿足 lx < rx 且曼哈頓距離 |lx-rx|+|ly-ry| ≤ 3。求最短總時間，不可達輸出 -1。

狀態建模

狀態 = (x, y, foot)，其中 foot = 0/1 表示**下一步移動哪隻腳**（或當前腳位置）。起始：底行所有 'S' 位置，左腳/右腳均可作為第一步，時間 0。
轉移：若當前腳為左（foot=0），枚舉右腳可能位置（dx∈[-2,2], dy∈[1,3], |dx|+|dy|≤3）；若為右腳，枚舉左腳位置（dy∈[-3,-1]）。目標格非 'X'，若為 'T' 更新答案，否則新時間 = 當前時間 + 格子數字，推入 SPFA 隊列。

SPFA 實現

維護 dist[foot][x][y] 最短時間。隊列存 (x,y,time,foot)。鬆弛條件：新時間 < 當前記錄時間。終止條件：隊列空。答案為所有到達 'T' 的最小時間。

代碼框架

#include <bits/stdc++.h>
using namespace std;
const int MAXH = 65, MAXW = 35, INF = 1e9;
char grid[MAXH][MAXW];
int dist[2][MAXH][MAXW];
int h, w;

struct State { int x, y, t, foot; };

bool inside(int x, int y) { return x>=0 && x=0 && y> w >> h, w||h) {
        for (int i=0;i> grid[i][j];
        for (int f=0;f<2;++f) for (int i=0;i q;
        for (int j=0;j 3) continue;
                    nx = cur.x + dx; ny = cur.y + ady;
                    if (!inside(nx,ny)) continue;
                    if (grid[nx][ny]=='T') { ans = min(ans, cur.t); continue; }
                    nt = cur.t + (grid[nx][ny]-'0');
                    if (nt < dist[nfoot][nx][ny]) {
                        dist[nfoot][nx][ny] = nt;
                        q.push({nx,ny,nt,nfoot});
                    }
                }
            }
        }
        cout << (ans==INF ? -1 : ans) << "\n";
    }
    return 0;
}

關鍵細節

1. 雙腳交替：狀態攜帶 foot，轉移時翻轉。
2. 曼哈頓距離約束：|dx|+|dy|≤3 且 lx（代碼中通過 dy 正負隱含保證）。
3. 起始狀態雙腳入隊：第一步可用左腳或右腳踏 'S'。
4. SPFA 適用性：邊權非負（0~9），也可用 Dijkstra，但 SPFA 寫法簡短且數據範圍小（≤ 60×30×2=3600 狀態）足夠快。