洛谷 P1135 奇怪的电梯

// P1135 奇怪的电梯 —— 状态图 BFS（★ 这一版就能 AC）
//
// 题目：N 层楼，第 i 层写着 K[i]。在第 i 层只能按「上」或「下」，
//       一次正好走 K[i] 层（越界就按不动）。问从 A 到 B 最少按几次，到不了输出 -1。
//
// ★ 又是一次「把格子换成状态」：
//     一个「点」= 你现在在第几层（1 ~ N）
//     一条「边」= 按一次按钮：i → i + K[i]，或 i → i − K[i]
//   BFS 一个字不用改，第一次到达 B 就是最少按键次数。
//
// ⚠⚠ 而这张图和前面几道**有一个根本区别：它的边是有向的。**
//   在第 i 层能上到 i + K[i]，可站在 i + K[i] 上时，能走多远由 **K[i + K[i]]** 说了算 ——
//   回不回得来完全是另一回事。
//   ⇒ [P1379](/sol/p1379/) 那页「从目标态反着 BFS 一次就够」的技巧，
//     在这道题上**直接就错**（p1135RevBad.cpp）；要反着做必须**先建反图**（p1135Rev.cpp）。
//
// ⚠ 两个边界：K[i] 可能是 0（原地不动 —— 一个自环，没有 vis 就死循环了）；A 可能等于 B（答案 0）。
//
// 复杂度 O(N)：每层最多进队一次，每层最多两条出边。N ≤ 200，小得离谱。

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

int main() {
    int n, a, b;
    if (scanf("%d %d %d", &n, &a, &b) != 3) return 0;
    vector<int> k(n + 1);
    for (int i = 1; i <= n; i++)
        if (scanf("%d", &k[i]) != 1) return 0;

    vector<int> dist_(n + 1, -1);
    queue<int> q;
    dist_[a] = 0;
    q.push(a);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (cur == b) break;
        for (int nxt : {cur + k[cur], cur - k[cur]}) {
            if (nxt < 1 || nxt > n) continue;
            if (dist_[nxt] != -1) continue;      // ★ 入队时就标记 —— K[i] = 0 的自环也靠它挡住
            dist_[nxt] = dist_[cur] + 1;
            q.push(nxt);
        }
    }

    printf("%d\n", dist_[b]);                    // 到不了就是 -1，正是题面要的
    return 0;
}

// ⚠⚠ 错法：照搬「从终点反着 BFS」这个技巧 —— 可这张图的边是**有向**的
//
// [P1379](/sol/p1379/) 那页刚说过：八数码的每一步都可逆 ⇒ 状态图的边是无向的
// ⇒ 从目标态反着 BFS 一次，整张表就出来了。
// [P1747](/sol/p1747/)（12 个方向成对相反）和 [P1332](/sol/p1332/)（网格）也一样。
//
// 于是很自然会想：这道题也从 B 反着走呗。而**这道题的边是有向的**：
//
//     在第 i 层，能走到 i ± K[i]                     <- 步长由**出发那层**的 K 决定
//     站在第 j 层想「反着走回 i」，走的却是 j ± K[j]  <- 步长换成了**落脚那层**的 K
//
// ⇒ 这一版从 B 出发、照着 `j ± K[j]` 走，**求的根本不是这道题的答案**
//   （它求的是「从 B 出发能不能到 A」，而那是另一个问题）。
//
// ★ 草稿在这儿写过「它在官方样例上照样给 3」—— **跑一遍就被打回来了**：
//   样例里 B = 5 而 K[5] = 5，从第 5 层按上是 10 层、按下是 0 层，**两个方向都出界** ——
//   它一步都走不了，直接输出 -1。⇒ **这一版官方样例就挡得住。**
//   ⚠ 但别把「样例挡得住」当成它无害：只要终点那层的 K 走得通，它就会给出一个
//   像模像样的错数字。抓获率见 p1135Count.cpp 第 ③ 段。
//
// ⚠ 要反着做**不是不行**，但必须**先建反图**（把每条 i → i ± K[i] 反过来存），
//   那一版是 p1135Rev.cpp，它和正解逐字节相同。

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

int main() {
    int n, a, b;
    if (scanf("%d %d %d", &n, &a, &b) != 3) return 0;
    vector<int> k(n + 1);
    for (int i = 1; i <= n; i++)
        if (scanf("%d", &k[i]) != 1) return 0;

    vector<int> dist_(n + 1, -1);
    queue<int> q;
    dist_[b] = 0;                                // ⚠⚠ 从终点出发……
    q.push(b);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (cur == a) break;
        for (int nxt : {cur + k[cur], cur - k[cur]}) {   // ⚠⚠ ……却还是照着「当前层」的 K 走
            if (nxt < 1 || nxt > n) continue;
            if (dist_[nxt] != -1) continue;
            dist_[nxt] = dist_[cur] + 1;
            q.push(nxt);
        }
    }

    printf("%d\n", dist_[a]);
    return 0;
}

// ★ 真想反着做，得先建反图 —— 这一版和正解逐字节相同
//
// 正图的边是 `i → i + K[i]` 和 `i → i − K[i]`（步长由**出发那层**决定）。
// 反图就是把每一条边掉个头：对每个 i，把 i 挂到 `i + K[i]` 和 `i − K[i]` 的入边表里。
//
// ⇒ 在反图上从 B 做 BFS，得到的就是「每一层到 B 要按几次」，查 A 即可。
//
// ★ 它和正解一样对，但要多存一张邻接表。
//   放它在这儿只为了说清一件事：**「反着跑一次」这个技巧本身没问题，
//   出问题的是「边有方向时还照着正图走」**（p1135RevBad.cpp）。

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

int main() {
    int n, a, b;
    if (scanf("%d %d %d", &n, &a, &b) != 3) return 0;
    vector<int> k(n + 1);
    for (int i = 1; i <= n; i++)
        if (scanf("%d", &k[i]) != 1) return 0;

    vector<vector<int>> rev(n + 1);              // rev[j] = 「一步能走到 j」的那些层
    for (int i = 1; i <= n; i++)
        for (int j : {i + k[i], i - k[i]})
            if (j >= 1 && j <= n) rev[j].push_back(i);

    vector<int> dist_(n + 1, -1);
    queue<int> q;
    dist_[b] = 0;
    q.push(b);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (cur == a) break;
        for (int nxt : rev[cur]) {
            if (dist_[nxt] != -1) continue;
            dist_[nxt] = dist_[cur] + 1;
            q.push(nxt);
        }
    }

    printf("%d\n", dist_[a]);
    return 0;
}

// ⚠⚠ 错法：BFS 忘了「入队时就标记」
//
// 第 14 章正文写死过一句：**标记要打在入队的时候**。在网格上忘了它，
// 后果是「退化成暴力」（[P1443](/sol/p1443/) 那页量过：入队次数爆炸，但答案还对）。
//
// ⚠ 而在这道题上，后果直接是**死循环**，理由是题面给的一个边界：
//
//     K[i] 的范围是 0 ≤ K[i] ≤ N   —— **K[i] 可以是 0**
//
//   `K[i] = 0` 那一层上，「上」和「下」都走到它自己 —— 那是一个**自环**。
//   没有 vis 的话，队列里立刻开始 i → i → i → …，永远出不来。
//   ★ 就算没有 K[i] = 0，只要图里有环（这题多得是），照样出不来。
//
// ⚠ 这一版自带一道闸：入队次数超上限就报出来并退出，
//   **绝不悄悄少入几次队把自己救活**（[P1443](/sol/p1443/) 那条教训）。

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

const long long PUSH_LIMIT = 20000000LL;

int main() {
    int n, a, b;
    if (scanf("%d %d %d", &n, &a, &b) != 3) return 0;
    vector<int> k(n + 1);
    for (int i = 1; i <= n; i++)
        if (scanf("%d", &k[i]) != 1) return 0;

    vector<int> dist_(n + 1, -1);
    queue<pair<int, int>> q;                     // (层, 已经按了几次)
    q.push({a, 0});
    long long pushes = 1;

    while (!q.empty()) {
        auto [cur, d0] = q.front();
        q.pop();
        if (cur == b) { printf("%d\n", d0); return 0; }
        for (int nxt : {cur + k[cur], cur - k[cur]}) {
            if (nxt < 1 || nxt > n) continue;
            // ⚠⚠ 这里本来该有一句 if (dist_[nxt] != -1) continue;
            q.push({nxt, d0 + 1});
            if (++pushes > PUSH_LIMIT) {
                fprintf(stderr, "入队次数超过 %lld —— 没有 vis，它出不来了\n", PUSH_LIMIT);
                return 1;
            }
        }
    }

    printf("%d\n", -1);
    return 0;
}

// P1135 对拍生成器：`./p1135Gen <seed> [maxN] [K 取 0 的百分比]`
//
// 输出：`n a b` ＋ 一行 n 个 K[i]。
//
// ★ 两个旋钮：
//   · maxN     —— 楼层数（1 ~ maxN 随机），默认 8；
//   · zeroPct  —— 每一层的 K 有多大概率取 0，默认 10。
//     ⚠ `K[i] = 0` 是题面明写允许的（`0 ≤ K[i] ≤ N`），而它正是
//       p1135NoVis.cpp（忘了入队标记）的那个自环 —— 把它调到 0 就等于亲手撤掉一档数据。

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

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1u;
    int maxN = argc > 2 ? atoi(argv[2]) : 8;
    int zeroPct = argc > 3 ? atoi(argv[3]) : 10;
    if (maxN < 1) maxN = 1;
    if (zeroPct < 0) zeroPct = 0;
    if (zeroPct > 100) zeroPct = 100;

    mt19937 rng(seed);
    int n = (int)(rng() % (unsigned)maxN) + 1;
    int a = (int)(rng() % (unsigned)n) + 1;
    int b = (int)(rng() % (unsigned)n) + 1;

    printf("%d %d %d\n", n, a, b);
    for (int i = 1; i <= n; i++) {
        int k = ((int)(rng() % 100u) < zeroPct) ? 0 : (int)(rng() % (unsigned)(n + 1));
        printf("%d%c", k, i == n ? '\n' : ' ');
    }
    return 0;
}

// P1135 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1135Count`      人看的版本
// `./p1135Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 四段：
//   ① ★★★ 这张图**有多有向**：一条边 i → j 里，反过来 j → i 也存在的占多少；
//   ② ⚠ 忘了「入队时标记」的后果：K[i] = 0 的自环 ⇒ 入队次数直接爆掉；
//   ③ 「照搬反着 BFS」那个错法的抓获率（沿楼层数 n 走）；
//   ④ 「到不了」有多常见 —— `-1` 不是摆设。

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

static bool CSV = false;

static void row(const char* key, const vector<long long>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (long long x : v) printf(",%lld", x);
    printf("\n");
}

/** 照生成器造一组数据（和 p1135Gen.cpp 逐字一致）。 */
static void gen(unsigned seed, int maxN, int zeroPct, int& n, int& a, int& b, vector<int>& k) {
    mt19937 rng(seed);
    n = (int)(rng() % (unsigned)maxN) + 1;
    a = (int)(rng() % (unsigned)n) + 1;
    b = (int)(rng() % (unsigned)n) + 1;
    k.assign(n + 1, 0);
    for (int i = 1; i <= n; i++)
        k[i] = ((int)(rng() % 100u) < zeroPct) ? 0 : (int)(rng() % (unsigned)(n + 1));
}

/** 正解：从 a 出发正着 BFS。 */
static int solve(int n, int a, int b, const vector<int>& k) {
    vector<int> d(n + 1, -1);
    queue<int> q;
    d[a] = 0;
    q.push(a);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (cur == b) break;
        for (int nxt : {cur + k[cur], cur - k[cur]}) {
            if (nxt < 1 || nxt > n || d[nxt] != -1) continue;
            d[nxt] = d[cur] + 1;
            q.push(nxt);
        }
    }
    return d[b];
}

/** 错法：从 b 出发，却还是照着「当前层」的 K 走。 */
static int solveRevBad(int n, int a, int b, const vector<int>& k) {
    vector<int> d(n + 1, -1);
    queue<int> q;
    d[b] = 0;
    q.push(b);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (cur == a) break;
        for (int nxt : {cur + k[cur], cur - k[cur]}) {
            if (nxt < 1 || nxt > n || d[nxt] != -1) continue;
            d[nxt] = d[cur] + 1;
            q.push(nxt);
        }
    }
    return d[a];
}

int main(int argc, char** argv) {
    CSV = (argc > 1 && string(argv[1]) == "csv");

    /* ① 这张图有多「有向」 */
    {
        long long edges = 0, both = 0, selfLoop = 0;
        for (unsigned seed = 1; seed <= 300; seed++) {
            int n, a, b; vector<int> k;
            gen(seed, 60, 10, n, a, b, k);
            for (int i = 1; i <= n; i++)
                for (int j : {i + k[i], i - k[i]}) {
                    if (j < 1 || j > n) continue;
                    edges++;
                    if (j == i) { selfLoop++; both++; continue; }
                    // 反过来那条边在不在：站在 j 上，一步能不能回到 i
                    if (j + k[j] == i || j - k[j] == i) both++;
                }
        }
        if (!CSV)
            printf("① 这张图有多「有向」（300 组随机数据，楼层 ≤ 60）：\n"
                   "   一共 %lld 条边，其中「反过来也走得通」的只有 %lld 条（%.1f%%）；自环 %lld 条\n"
                   "   ⇒ 绝大多数边是**单向**的 —— 所以「从终点反着照正图走」求的根本不是这道题\n\n",
                   edges, both, 100.0 * (double)both / (double)edges, selfLoop);
        row("edges", {edges, both, selfLoop});
    }

    /* ② 忘了入队标记：入队次数 */
    {
        // 一个最小的例子：3 层，K = {0, 1, 1}，从 1 走到 3
        //   第 1 层 K = 0 ⇒ 自环，没有 vis 的话队列里永远是它自己
        vector<int> k = {0, 0, 1, 1};
        long long pushes = 1;
        queue<int> q;
        q.push(1);
        bool blew = false;
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            if (cur == 3) break;
            for (int nxt : {cur + k[cur], cur - k[cur]}) {
                if (nxt < 1 || nxt > 3) continue;
                q.push(nxt);
                if (++pushes > 10000000LL) { blew = true; break; }
            }
            if (blew) break;
        }
        if (!CSV)
            printf("② 忘了「入队时标记」：3 层、K = {0, 1, 1}、从 1 走到 3 ——\n"
                   "   %s（第 1 层 K = 0 是个自环，队列里出不来）\n\n",
                   blew ? "入队 1000 万次还没完，掐掉" : "居然跑完了？");
        row("noVisBlew", {blew ? 1 : 0});
    }

    /* ③ 「照搬反着 BFS」的抓获率 */
    {
        vector<long long> caught;
        vector<int> ns = {4, 8, 20, 60};
        if (!CSV) printf("③ 「从终点反着照正图走」那个错法的抓获率（300 轮）：\n");
        for (int maxN : ns) {
            int c = 0;
            for (unsigned seed = 1; seed <= 300; seed++) {
                int n, a, b; vector<int> k;
                gen(seed, maxN, 10, n, a, b, k);
                if (solve(n, a, b, k) != solveRevBad(n, a, b, k)) c++;
            }
            caught.push_back(c);
            if (!CSV) printf("   楼层 ≤ %2d：%3d / 300\n", maxN, c);
        }
        if (!CSV) printf("\n");
        row("revBadCatch", caught);
    }

    /* ④ 「到不了」有多常见 */
    {
        vector<long long> unreach;
        vector<int> ns = {4, 8, 20, 60};
        if (!CSV) printf("④ 正解输出 -1（到不了）的比例（300 轮）：\n");
        for (int maxN : ns) {
            int c = 0;
            for (unsigned seed = 1; seed <= 300; seed++) {
                int n, a, b; vector<int> k;
                gen(seed, maxN, 10, n, a, b, k);
                if (solve(n, a, b, k) == -1) c++;
            }
            unreach.push_back(c);
            if (!CSV) printf("   楼层 ≤ %2d：%3d / 300\n", maxN, c);
        }
        if (!CSV) printf("   ⇒ -1 不是摆设，随手造的数据里就有一大半到不了\n\n");
        row("unreach", unreach);

        /* ⑤ ★★★ 第 ③ 段那条抓获率曲线为什么会掉头：把「两版都输出 -1」的轮次剔掉再看
         *   （[P1746](/sol/p1746/) 那条：「一致」有两种 —— 都算对了，和都没算。） */
        vector<long long> solvable, caughtIn;
        if (!CSV) printf("⑤ 把「正解就是 -1」的轮次剔掉，再看那个错法的抓获率：\n");
        for (size_t t = 0; t < ns.size(); t++) {
            int maxN = ns[t];
            int tot = 0, c = 0;
            for (unsigned seed = 1; seed <= 300; seed++) {
                int n, a, b; vector<int> k;
                gen(seed, maxN, 10, n, a, b, k);
                int ref = solve(n, a, b, k);
                if (ref == -1) continue;
                tot++;
                if (ref != solveRevBad(n, a, b, k)) c++;
            }
            solvable.push_back(tot);
            caughtIn.push_back(c);
            if (!CSV)
                printf("   楼层 ≤ %2d：有解的 %3d 轮里抓到 %3d 轮（%.1f%%）\n",
                       maxN, tot, c, 100.0 * (double)c / (double)tot);
        }
        if (!CSV) printf("   ⇒ 曲线不再掉头 —— 掉下去的那一段是「两版一起输出 -1」\n\n");
        row("solvable", solvable);
        row("caughtInSolvable", caughtIn);
    }
    return 0;
}