傳送點 題解｜APCS 2019 年 10 月中高級 第 3 題

前置知識

這題的核心（怎麼把「按一次鍵」變成圖上的一條邊）下面會從頭講；要先會的是：

• BFS：NTUCPC Guide〈BFS〉——要帶走的是「邊權都一樣時，用佇列一層一層往外找，第一次碰到某個點時走的步數就是最少步數」。吳邦一《AP325》第 7 章 7.2.2 的 BFS 一節與例題 P-7-1 探索距離，習題 Q-7-5 闖關路線就是本題（教材 PDF 第 236～241、252～253 頁；Python 版第 7 章（I））。
• 佇列：NTUCPC Guide〈Stack、Queue 與 Deque〉——queue<int> 的 push、front、pop。

簡潔題意

位置 \(0\) 到 \(n - 1\) 排成一列，從 \(0\) 出發、目標是 \(P\)。一次操作：從目前位置 \(u\) 先走到 \(v = u - L\) 或 \(v = u + R\)，\(v\) 必須在 \(0\) 到 \(n - 1\) 之間；踩到 \(v\) 會立刻被傳送到 \(S_v\)，\(S_v\) 不在範圍內的話這個操作不能用。一次操作只傳送一次，不會連鎖。求最少幾次操作能到 \(P\)，到不了輸出 \(-1\)，\(P = 0\) 輸出 \(0\)（\(2 \le n \le 10^6\)，\(1 \le L, R \le \lfloor n / 2 \rfloor\)，\(|S_i| \le 10^8\)，\(S_0 = 0\)、\(S_P = P\)）。（APCS 逐筆給分。）

把每一次操作畫成一條邊

每個位置當成圖上的一個點。從 \(u\) 按一次鍵，能到的地方只有兩種：往左踩 \(u - L\) 然後落在 \(S_{u - L}\)、往右踩 \(u + R\) 然後落在 \(S_{u + R}\)——所以每個點最多兩條有向邊，終點是 \(S_v\) 而不是 \(v\)；踩的位置或傳送的終點只要有一個出界，那條邊就不存在。範例的五個點與邊見圖 1。

每條邊都代表「一次操作」，所以「最少幾次操作」就是「從 \(0\) 到 \(P\) 最少走幾條邊」。邊權都是 \(1\) 的最短路用 BFS：從 \(0\) 開始，先找出一步能到的所有點、再找兩步能到的……用佇列維持「先發現的先處理」，dist[u] 記第一次到達 \(u\) 時走了幾步。某個點第一次被發現時，它的步數一定是最少的——比它更少步能到的點，全部都在它前面被處理完了。

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1000000;
int S[MAX_N];                    // S[v] = 走到 v 會被傳送到哪裡
int dist[MAX_N];                 // dist[u] = 從 0 到 u 最少幾次操作；-1 ＝ 還沒到過

int main() {
    int n, P, L, R;
    cin >> n >> P >> L >> R;
    for (int i = 0; i < n; i++) cin >> S[i];
    for (int i = 0; i < n; i++) dist[i] = -1;
    queue<int> q;
    dist[0] = 0;
    q.push(0);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int d = 0; d < 2; d++) {            // 兩種操作：往左 L 格、往右 R 格
            int v;
            if (d == 0) v = u - L;
            else v = u + R;
            if (v < 0 || v >= n) continue;       // 走出去了，這個操作不能用
            int to = S[v];                       // 踩到 v 立刻被傳送到 S[v]
            if (to < 0 || to >= n) continue;     // 傳送到界外，這個操作也不能用
            if (dist[to] != -1) continue;        // 已經到過：之前那次一定不會更多步
            dist[to] = dist[u] + 1;
            q.push(to);
        }
    }
    cout << dist[P] << endl;                     // 到不了就還是 -1，剛好就是題目要的
    return 0;
}

幾個細節：

• 兩個範圍檢查缺一不可：先檢查踩的位置 \(v\)，再檢查傳送的終點 \(S_v\)。\(S_v\) 可以是負的或超過 \(n - 1\)，直接拿去當索引會讀到陣列外面。
• 到不了的點 dist 停在 \(-1\)，正好是題目要的輸出；\(P = 0\) 時 dist[0] = 0 也自動對。
• 每個點最多進佇列一次、檢查兩條邊，\(O(n)\)；\(n = 10^6\) 的輸入約 \(10\) MB，本站實測 \(0.42\) 秒。

測過再交：範例沒有「到不了」

範例兩步就到、每個操作都合法；沒蓋到的是：\(P = 0\)、\(S_v\) 出界的操作、完全到不了、「傳送只做一次」、第一次碰到不一定最短的情況，以及 \(n = 10^6\) 的長鏈。

七筆都親眼看過正確，這題就穩了。