洛谷 P1379 八数码难题

// P1379 八数码难题 —— 状态图上的 BFS（★ 这一版就能 AC）
//
// 题目：3 × 3 棋盘，八个棋子（1~8）＋ 一个空格（0）。空格周围的棋子可以移进空格。
//       给定初始布局，问最少几步能变成目标布局 `123804765`。
//
// ★ 关键的一步：**把「格子」换成「状态」**。
//   第 14 章的 BFS 走在网格上：一个格子是一个点，上下左右是边。
//   这道题走在**状态图**上：
//
//       一个「点」   = 棋盘的一种摆法（九个数字，写成一个长度 9 的字符串）
//       一条「边」   = 挪一次空格（空格和它上下左右某个棋子交换）
//
//   一旦接受这个抽象，BFS 一个字都不用改：第一次到达 = 最短。
//
// ⚠⚠ 而这道题**全部的难点就在「邻居是什么」**上：
//   状态存成字符串之后，很容易顺手用一维下标 `i ± 1` / `i ± 3` 去找邻居 ——
//   `i ± 3` 是对的（上下），可 **`i ± 1` 会跨行**：下标 2 的右边不是下标 3，
//   下标 2 已经在第 0 行最右边了。那一版见 p1379Flat.cpp。
//
// 状态用 map<string,int> 存距离：可达状态一共 181440 个（p1379Count.cpp 第 ② 段），
// 每个状态最多 4 个邻居 —— 规模很小，map 完全够用。

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

const string GOAL = "123804765";

int main() {
    string s;
    if (!(cin >> s)) return 0;

    map<string, int> dist_;
    queue<string> q;
    dist_[s] = 0;
    q.push(s);

    while (!q.empty()) {
        string cur = q.front();
        q.pop();
        if (cur == GOAL) { cout << dist_[cur] << "\n"; return 0; }

        int p = (int)cur.find('0');
        int r = p / 3, c = p % 3;                  // ★ 先还原成行列，再判边界
        const int DR[4] = {-1, 1, 0, 0};
        const int DC[4] = {0, 0, -1, 1};
        for (int k = 0; k < 4; k++) {
            int nr = r + DR[k], nc = c + DC[k];
            if (nr < 0 || nr > 2 || nc < 0 || nc > 2) continue;
            string nxt = cur;
            swap(nxt[p], nxt[nr * 3 + nc]);
            if (dist_.count(nxt)) continue;        // ⚠ 用 count 查，别用 dist_[nxt]（那会插进去）
            dist_[nxt] = dist_[cur] + 1;
            q.push(nxt);
        }
    }

    cout << -1 << "\n";                            // 题面保证不会走到这儿
    return 0;
}

// ⚠⚠ 错法：状态是字符串，就顺手用一维下标 ±1 / ±3 找邻居
//
// 状态存成 "283104765" 这样的字符串之后，空格的位置就是一个下标 `p`。
// 「上下左右」写成 `p - 3 / p + 3 / p - 1 / p + 1` 看着天经地义 ——
// 上下那两个是对的，**左右那两个会跨行**：
//
//       下标：  0 1 2        p = 2 在第 0 行最右边，
//               3 4 5        它的 `p + 1` 是下标 3 —— 那是第 1 行最左边，
//               6 7 8        棋盘上这两格根本不挨着。
//
// ★★★ 草稿在这儿写过一句判词，**被实测打回来了**，值得原样记下来：
//
//   「八数码的合法移动保持一个不变量 —— 去掉 0 之后那八个数字的逆序对数奇偶性不变，
//     9! 种摆法正好被劈成互不相通的两半（各 181440）；而跨行移动打破了这个不变量，
//     ⇒ 这一版能到达的状态数会从 181440 变成 362880。」
//
//   **实测：还是 181440。** 原因一句话 ——
//   横向挪空格（不管跨不跨行）在「去掉 0 的那八个数字」里，
//   只是让 0 从某个棋子的左边挪到右边，**棋子之间的相对顺序一点没动**
//   ⇒ 逆序对数根本不变。那 80640 条「跨行」的假边，**两端奇偶全都相同**（逐条验过）。
//
// ⇒ 那它到底干了什么？**把路走短了。**（p1379Count.cpp 第 ③ 段）
//
//     可达状态      181440  →  181440   （一个没变）
//     最远距离      30 步   →  28 步
//     被算小的状态          155579 / 181440（86%）
//
//   ⚠ 所以它是一个**只会把答案算小、永远不会算大**的 bug：
//     离目标越远越容易现形，而**官方样例只有 4 步 —— 挡不住它**。

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

const string GOAL = "123804765";

int main() {
    string s;
    if (!(cin >> s)) return 0;

    map<string, int> dist_;
    queue<string> q;
    dist_[s] = 0;
    q.push(s);

    while (!q.empty()) {
        string cur = q.front();
        q.pop();
        if (cur == GOAL) { cout << dist_[cur] << "\n"; return 0; }

        int p = (int)cur.find('0');
        const int D[4] = {-3, 3, -1, 1};           // ⚠⚠ 就是这一行：一维下标直接加减
        for (int k = 0; k < 4; k++) {
            int np = p + D[k];
            if (np < 0 || np > 8) continue;        // 只挡住了「掉出数组」，没挡住「跨行」
            string nxt = cur;
            swap(nxt[p], nxt[np]);
            if (dist_.count(nxt)) continue;
            dist_[nxt] = dist_[cur] + 1;
            q.push(nxt);
        }
    }

    cout << -1 << "\n";
    return 0;
}

// P1379 对拍生成器：`./p1379Gen <seed> [k] [mode]`
//
// ⚠ **不能随便打乱九个数字就当输入** —— 9! 种摆法里有一半根本到不了目标态
//   （逆序对奇偶性，p1379Count.cpp 第 ② 段）。随机排列有 50% 概率是无解的，
//   而题面明说「保证测试数据中无特殊无法到达目标状态数据」。
//   ⇒ 这是[第 13 章 P1162](/sol/p1162/) 那条的又一次现场：
//     **有一类题最难写的不是正解，是生成器** —— 先问「随手造的数据有多大概率是合法输入」。
//
// ★★★ 两个 mode，而这一页最值钱的一条就在它们的差别上：
//
//   mode 0（默认）：从目标态**倒着随机走 k 步**。造出来的一定有解 —— 可
//     ⚠⚠ **走 k 步不等于「距离 k」**：随机游走会绕回来。
//     实测（p1379Count.cpp 第 ⑤ 段）：倒着走 30 步，造出来的状态**平均只有 8.65 步远**，
//     而全图 181440 个状态的平均距离是 **21.50 步**。
//     ⇒ 这一档**永远待在目标附近**，对「把路走短」那类 bug 几乎瞎。
//
//   mode 1：先把整张状态图 BFS 一遍，**直接从「真实距离 ≥ k」的状态里随机挑**。
//     ⇒ 同一个 bug，mode 0 的 30 步档抓 49 / 300，mode 1 的 k = 25 档抓 **291 / 300**。

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

static const int DR[4] = {-1, 1, 0, 0};
static const int DC[4] = {0, 0, -1, 1};

/** mode 1 用：把整张状态图从目标态 BFS 一遍，挑出「距离 ≥ k」的那些状态。 */
static vector<string> farStates(int k) {
    unordered_map<string, int> d;
    queue<string> q;
    string goal = "123804765";
    d[goal] = 0;
    q.push(goal);
    while (!q.empty()) {
        string cur = q.front();
        q.pop();
        int p = (int)cur.find('0');
        for (int t = 0; t < 4; t++) {
            int nr = p / 3 + DR[t], nc = p % 3 + DC[t];
            if (nr < 0 || nr > 2 || nc < 0 || nc > 2) continue;
            string nxt = cur;
            swap(nxt[p], nxt[nr * 3 + nc]);
            if (d.count(nxt)) continue;
            d[nxt] = d[cur] + 1;
            q.push(nxt);
        }
    }
    vector<string> out;
    for (auto& [s, v] : d) if (v >= k) out.push_back(s);
    sort(out.begin(), out.end());          // ⚠ 排一下序，unordered_map 的遍历顺序不保证可复现
    return out;
}

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1u;
    int steps = argc > 2 ? atoi(argv[2]) : 30;
    int mode = argc > 3 ? atoi(argv[3]) : 0;
    if (steps < 0) steps = 0;

    mt19937 rng(seed);

    if (mode == 1) {                        // ★ 直接从远处挑
        vector<string> far = farStates(steps);
        printf("%s\n", far[rng() % far.size()].c_str());
        return 0;
    }

    string s = "123804765";

    for (int i = 0; i < steps; i++) {
        int p = (int)s.find('0');
        int r = p / 3, c = p % 3;
        vector<int> ok;
        for (int k = 0; k < 4; k++) {
            int nr = r + DR[k], nc = c + DC[k];
            if (nr < 0 || nr > 2 || nc < 0 || nc > 2) continue;
            ok.push_back(nr * 3 + nc);
        }
        int np = ok[rng() % ok.size()];
        swap(s[p], s[np]);
    }
    printf("%s\n", s.c_str());
    return 0;
}

// ★ 另一种写法：从**目标态**反着 BFS，一次把整张表铺出来
//
// 八数码的每一步移动都是**可逆的**（把棋子挪回去就行）——
// 也就是说这张状态图的边是**无向**的。于是
//
//     从初始态走到目标态的最少步数  ==  从目标态走到初始态的最少步数
//
// ⇒ 可以从**目标态**出发 BFS 一次，把 181440 个可达状态的距离全算出来，再 O(1) 查表。
//
// ⚠ 对这道题（一次只问一个初始态）它并不划算：正解走到目标就停了，
//   而这一版每次都要把整张图铺满。它的意义在别处 ——
//
// ★★★ **「反着跑一次就够」这句话缺一个主语：主语是这张图的边是不是无向的。**
//   这道题、[P1747](/sol/p1747/)（马 + 象的走法成对相反）、[P1332](/sol/p1332/)（网格）都成立；
//   而同一轮的 [P1135 奇怪的电梯](/sol/p1135/) 里，边是**有向**的
//   （在 i 层能上到 i + K[i]，回不来），同一个动作**当场就错**。

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

const string GOAL = "123804765";

int main() {
    string s;
    if (!(cin >> s)) return 0;

    map<string, int> dist_;
    queue<string> q;
    dist_[GOAL] = 0;                               // ★ 从目标态出发
    q.push(GOAL);

    while (!q.empty()) {
        string cur = q.front();
        q.pop();
        int p = (int)cur.find('0');
        int r = p / 3, c = p % 3;
        const int DR[4] = {-1, 1, 0, 0};
        const int DC[4] = {0, 0, -1, 1};
        for (int k = 0; k < 4; k++) {
            int nr = r + DR[k], nc = c + DC[k];
            if (nr < 0 || nr > 2 || nc < 0 || nc > 2) continue;
            string nxt = cur;
            swap(nxt[p], nxt[nr * 3 + nc]);
            if (dist_.count(nxt)) continue;
            dist_[nxt] = dist_[cur] + 1;
            q.push(nxt);
        }
    }

    auto it = dist_.find(s);
    cout << (it == dist_.end() ? -1 : it->second) << "\n";
    return 0;
}

// P1379 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1379Count`      人看的版本
// `./p1379Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 四段：
//   ① 从目标态 BFS 铺满：能到达多少个状态、最远几步；
//   ② ★★★ 换一条**和 BFS 完全无关**的路验它：逆序对奇偶性判据 ——
//      9! 种摆法按「去掉 0 之后逆序对数的奇偶」正好劈成两半，各多少个；
//   ③ ⚠ 一维下标 ±1 那个错法：它能到达多少状态（那个不变量被打破了）；
//   ④ 它的抓获率：从目标态倒着走 k 步造输入，正解和它差多少。

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

static bool CSV = false;
static const string GOAL = "123804765";

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");
}

/** 从 GOAL 出发 BFS。flat = true 时用一维下标 ±1 / ±3 找邻居（那个错法）。 */
static unordered_map<string, int> bfsAll(bool flat) {
    unordered_map<string, int> d;
    queue<string> q;
    d[GOAL] = 0;
    q.push(GOAL);
    const int DR[4] = {-1, 1, 0, 0};
    const int DC[4] = {0, 0, -1, 1};
    const int D1[4] = {-3, 3, -1, 1};
    while (!q.empty()) {
        string cur = q.front();
        q.pop();
        int p = (int)cur.find('0');
        for (int k = 0; k < 4; k++) {
            int np;
            if (flat) {
                np = p + D1[k];
                if (np < 0 || np > 8) continue;
            } else {
                int nr = p / 3 + DR[k], nc = p % 3 + DC[k];
                if (nr < 0 || nr > 2 || nc < 0 || nc > 2) continue;
                np = nr * 3 + nc;
            }
            string nxt = cur;
            swap(nxt[p], nxt[np]);
            if (d.count(nxt)) continue;
            d[nxt] = d[cur] + 1;
            q.push(nxt);
        }
    }
    return d;
}

/** 去掉 0 之后，那八个数字的逆序对数的奇偶。 */
static int parityOf(const string& s) {
    string t;
    for (char ch : s) if (ch != '0') t += ch;
    int inv = 0;
    for (size_t i = 0; i < t.size(); i++)
        for (size_t j = i + 1; j < t.size(); j++)
            if (t[i] > t[j]) inv++;
    return inv & 1;
}

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

    /* ① 从目标态铺满：可达状态数 ＋ 最远距离 ＋ 步数分布 */
    auto ok = bfsAll(false);
    long long reach = (long long)ok.size();
    int deepest = 0;
    string farthest;
    for (auto& [s, v] : ok) if (v > deepest || (v == deepest && s > farthest)) { deepest = max(deepest, v); }
    for (auto& [s, v] : ok) if (v == deepest) { farthest = s; break; }
    if (!CSV) {
        printf("① 从目标态 %s BFS 铺满：能到达 %lld 个状态，最远 %d 步（例如 %s）\n",
               GOAL.c_str(), reach, deepest, farthest.c_str());
        printf("   9! = %d，也就是说**一半的摆法根本到不了**\n\n", 362880);
    }
    row("reach", {reach, deepest});

    /* ② ★★★ 完全无关的第二条路：逆序对奇偶性 */
    {
        string base = "012345678";
        long long same = 0, diff = 0;
        int goalP = parityOf(GOAL);
        do {
            if (parityOf(base) == goalP) same++; else diff++;
        } while (next_permutation(base.begin(), base.end()));
        if (!CSV) {
            printf("② 换一条和 BFS 完全无关的路：**去掉 0 之后那八个数字的逆序对数奇偶性**，\n"
                   "   合法移动一步都改不了它。9! 种摆法里\n"
                   "     和目标态同奇偶的 %lld 个 ／ 不同的 %lld 个\n", same, diff);
            printf("   ⇒ 和第 ① 段那个 %lld %s\n\n", reach, same == reach ? "**一个不差**" : "对不上（出事了）");
        }
        row("parity", {same, diff, same == reach ? 1 : 0});
    }

    /* ③ ⚠ 一维下标 ±1 那个错法：它能到达多少状态、把多少个距离算小了
     *
     * ⚠⚠ 草稿在这儿写的是「跨行移动打破了奇偶不变量 ⇒ 可达状态数 181440 → 362880」。
     *   **实测把它打回来了：还是 181440。** 原因一句话就能说清 ——
     *   横向挪空格（不管跨不跨行）在「去掉 0 之后的那八个数字」里
     *   只是让 0 从一个棋子的左边挪到右边，**棋子之间的相对顺序一点没动**
     *   ⇒ 逆序对数根本不变，奇偶自然也不变。
     *   下面把这句话直接验一遍：把所有「跨行」的假边逐条拿出来，看两端奇偶是不是都一样。
     */
    {
        auto bad = bfsAll(true);
        long long reachBad = (long long)bad.size();
        int deepBad = 0;
        for (auto& [s, v] : bad) { (void)s; deepBad = max(deepBad, v); }

        // 那些「跨行」的假边：p 和 p+1 不在同一行（p = 2 或 5）
        long long fakeEdges = 0, fakeSameParity = 0;
        for (auto& [s, v] : ok) {
            (void)v;
            int p = (int)s.find('0');
            for (int np : {p - 1, p + 1}) {
                if (np < 0 || np > 8) continue;
                if (p / 3 == np / 3) continue;          // 同一行 —— 那是真边
                string t = s;
                swap(t[p], t[np]);
                fakeEdges++;
                if (parityOf(t) == parityOf(s)) fakeSameParity++;
            }
        }

        // 它把多少个状态的距离算小了
        long long shorter = 0, sameDist = 0;
        for (auto& [s, v] : ok) {
            auto it = bad.find(s);
            if (it == bad.end()) continue;
            if (it->second < v) shorter++;
            else if (it->second == v) sameDist++;
        }

        if (!CSV) {
            printf("③ 一维下标 ±1 那个错法（跨行也当成相邻）：能到达 %lld 个状态，最远 %d 步\n",
                   reachBad, deepBad);
            printf("   ⚠ 我以为可达数会翻倍（181440 → 362880），**实测没有** ——\n");
            printf("     那 %lld 条「跨行」的假边里，两端奇偶相同的有 %lld 条（横向挪 0 不动棋子的相对顺序）\n",
                   fakeEdges, fakeSameParity);
            printf("   ⇒ 它真正干的事是**把路走短了**：%lld 个可达状态里，"
                   "距离被算小的 %lld 个、不变的 %lld 个\n\n", reach, shorter, sameDist);
        }
        row("flatReach", {reachBad, deepBad});
        row("fakeEdges", {fakeEdges, fakeSameParity});
        row("flatShorter", {shorter, sameDist});
    }

    /* ④ 抓获率：从目标态倒着随机走 k 步造输入 */
    {
        auto bad = bfsAll(true);
        vector<long long> caught;
        vector<int> steps = {4, 10, 20, 30};
        const int DR[4] = {-1, 1, 0, 0};
        const int DC[4] = {0, 0, -1, 1};
        if (!CSV) printf("④ 从目标态倒着走 k 步造输入（300 轮），正解和那个错法差几次\n");
        for (int k : steps) {
            int c = 0;
            for (int seed = 1; seed <= 300; seed++) {
                mt19937 rng((unsigned)seed);
                string s = GOAL;
                for (int i = 0; i < k; i++) {
                    int p = (int)s.find('0');
                    vector<int> cand;
                    for (int t = 0; t < 4; t++) {
                        int nr = p / 3 + DR[t], nc = p % 3 + DC[t];
                        if (nr < 0 || nr > 2 || nc < 0 || nc > 2) continue;
                        cand.push_back(nr * 3 + nc);
                    }
                    swap(s[p], s[cand[rng() % cand.size()]]);
                }
                if (ok[s] != bad[s]) c++;
            }
            caught.push_back(c);
            if (!CSV) printf("   倒着走 %2d 步：%3d / 300\n", k, c);
        }
        if (!CSV) printf("\n");
        row("flatCatch", caught);

        /* ⑤ ★★★ 「86% 的状态答案是错的」和「300 轮只抓到 49 次」为什么不矛盾：
         *   **倒着随机走 k 步，造出来的不是「距离 k 的状态」** —— 随机游走会绕回来。
         *   下面把两件事量出来：生成器造出来的状态平均离目标多远、全图平均多远；
         *   以及换一种造法（直接从 BFS 表里挑远处的状态）抓获率会怎样。
         */
        {
            // 全图的平均距离
            long long sumAll = 0;
            for (auto& [s, v] : ok) { (void)s; sumAll += v; }
            long long avgAll100 = sumAll * 100 / reach;

            // 生成器各档造出来的状态，平均真实距离
            vector<long long> avgGen100;
            for (int k : steps) {
                long long sum = 0;
                for (int seed = 1; seed <= 300; seed++) {
                    mt19937 rng((unsigned)seed);
                    string s = GOAL;
                    for (int i = 0; i < k; i++) {
                        int p = (int)s.find('0');
                        vector<int> cand;
                        for (int t = 0; t < 4; t++) {
                            int nr = p / 3 + DR[t], nc = p % 3 + DC[t];
                            if (nr < 0 || nr > 2 || nc < 0 || nc > 2) continue;
                            cand.push_back(nr * 3 + nc);
                        }
                        swap(s[p], s[cand[rng() % cand.size()]]);
                    }
                    sum += ok[s];
                }
                avgGen100.push_back(sum * 100 / 300);
            }

            // 换一种造法：直接从「真实距离 ≥ 25」的状态里挑
            vector<string> far;
            for (auto& [s, v] : ok) if (v >= 25) far.push_back(s);
            sort(far.begin(), far.end());
            int cFar = 0;
            for (int seed = 1; seed <= 300; seed++) {
                mt19937 rng((unsigned)seed);
                const string& s = far[rng() % far.size()];
                if (ok[s] != bad[s]) cFar++;
            }
            if (!CSV) {
                printf("⑤ 为什么「86%% 的状态是错的」和「300 轮只抓到 49 次」不矛盾：\n");
                printf("   全图 %lld 个状态的平均距离是 %.2f 步；\n", reach, avgAll100 / 100.0);
                for (size_t i = 0; i < steps.size(); i++)
                    printf("   倒着随机走 %2d 步，造出来的状态平均只有 %.2f 步远\n",
                           steps[i], avgGen100[i] / 100.0);
                printf("   ⇒ **随机游走会绕回来，走 k 步 ≠ 距离 k。**\n");
                printf("   换一种造法：直接从「真实距离 ≥ 25」的 %zu 个状态里随机挑 —— 抓到 %d / 300\n\n",
                       far.size(), cFar);
            }
            row("avgDist", {avgAll100});
            row("avgGen", avgGen100);
            row("farCatch", {(long long)far.size(), cFar});
        }
    }
    return 0;
}