洛谷 P2324 [SCOI2005] 骑士精神

// P2324 的**中间版**：只有迭代加深，**没有估价函数**（也就是本章第 3 步那一版）。
//
// 题目：5 × 5 棋盘，12 个白骑士（0）、12 个黑骑士（1）、一个空位（*）。
//       每步把**任意一个骑士按马的走法跳到空位上**（等价于「空位按马的走法挪一格」）。
//       问最少几步能变成目标棋盘；**15 步以内**给不出就输出 -1。
//
// 它**是对的**，而且深度上限 15 是题面给的、不用自己猜。可它跑不完：
//   每层 8 个分支、15 层是 `8¹⁵ ≈ 3.5 × 10¹³`。
//
// ⚠⚠ 官方样例的第二组答案是 -1 —— 那意味着它要**把 15 层整棵树搜完**才敢下结论。
//   ⇒ 这一版在官方样例上就跑不出来。页面第 ③ 步给它加了节点上限去量它到底走多远。
//
// ⇒ 差的那一步就是估价函数（p2324.cpp）：一句 `depth + h > limit` 而已。

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

static const char* TARGET = "1111101111"  "00*11"  "00001"  "00000";
static const int DX[8] = {1, 1, -1, -1, 2, 2, -2, -2};
static const int DY[8] = {2, -2, 2, -2, 1, -1, 1, -1};

static char s[26];
static int limitDepth;
static long long nodes = 0;

/** 还有几个骑士不在位（★ 空位那一格不算） */
static int hval() {
    int c = 0;
    for (int i = 0; i < 25; i++) if (s[i] != '*' && s[i] != TARGET[i]) c++;
    return c;
}

static bool dfs(int depth, int pos) {       // pos = 空位在哪
    nodes++;
    if (hval() == 0) return true;
    if (depth >= limitDepth) return false;         // ★ 只有深度上限，没有估价
    int x = pos / 5, y = pos % 5;
    for (int t = 0; t < 8; t++) {
        int nx = x + DX[t], ny = y + DY[t];
        if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
        int np = nx * 5 + ny;
        swap(s[pos], s[np]);
        if (dfs(depth + 1, np)) { swap(s[pos], s[np]); return true; }
        swap(s[pos], s[np]);
    }
    return false;
}

int main(int argc, char** argv) {
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        string row, all;
        for (int i = 0; i < 5; i++) { cin >> row; all += row; }
        memcpy(s, all.c_str(), 25);
        s[25] = 0;
        int pos = (int)all.find('*');
        int ans = -1;
        for (limitDepth = 0; limitDepth <= 15; limitDepth++)      // ★ 迭代加深
            if (dfs(0, pos)) { ans = limitDepth; break; }
        cout << ans << "\n";
    }
    if (argc > 1 && string(argv[1]) == "count") cerr << "nodes=" << nodes << "\n";
    return 0;
}

// P2324 骑士精神 —— IDA*（★ 这一版就能 AC）
//
// 题目：5 × 5 棋盘，12 个白骑士（0）、12 个黑骑士（1）、一个空位（*）。
//       每步把**任意一个骑士按马的走法跳到空位上**（等价于「空位按马的走法挪一格」）。
//       问最少几步能变成目标棋盘；**15 步以内**给不出就输出 -1。
//
// ★ 题面那句「15 步以内」不是装饰，它是**这道题能做的全部理由**：
//   状态空间是 `25 × C(24,12) ≈ 6.8 × 10⁷`，BFS 存得下但十组数据存不起；
//   而深度被钉死在 15 ⇒ **迭代加深**（第 18 章第 3 步）正好用得上：
//   从 1 到 15 逐个试深度上限，第一个搜得到的就是答案。
//
// ⚠ 光有迭代加深还不够：每层 8 个分支、15 层是 8¹⁵ ≈ 3.5 × 10¹³。
//   ⇒ 必须加**估价函数**，也就是本章第 7 步的 IDA*：
//
// ★★★ 估价函数 h(s) = **还有几个骑士不在自己该在的位置上**（空位不算）。
//   为什么它是对的 —— 一句话：**一步只能让一个骑士归位**
//   （每步只有一个骑士动，它顶多从「不在位」变成「在位」）。
//   ⇒ 至少还要 h 步 ⇒ `已走步数 + h > 深度上限` 时这条路必然超，直接回头。
//
// ⚠⚠ 这个「空位不算」不能省：把空位也算进去，h 就可能**比真实步数还大**（高估），
//   于是它会把**正确的那条路也剪掉** —— 那一版见 p2324Over.cpp，
//   而它的错法很有欺骗性：**答案不是偏小，是偏大或者变成 -1**。

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

static const char* TARGET = "1111101111"  "00*11"  "00001"  "00000";
static const int DX[8] = {1, 1, -1, -1, 2, 2, -2, -2};
static const int DY[8] = {2, -2, 2, -2, 1, -1, 1, -1};

static char s[26];
static int limitDepth;
static long long nodes = 0;

/** 还有几个骑士不在位（★ 空位那一格不算） */
static int hval() {
    int c = 0;
    for (int i = 0; i < 25; i++) if (s[i] != '*' && s[i] != TARGET[i]) c++;
    return c;
}

static bool dfs(int depth, int pos) {       // pos = 空位在哪
    nodes++;
    int h = hval();
    if (h == 0) return true;
    if (depth + h > limitDepth) return false;      // ★ IDA* 的那一刀
    int x = pos / 5, y = pos % 5;
    for (int t = 0; t < 8; t++) {
        int nx = x + DX[t], ny = y + DY[t];
        if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
        int np = nx * 5 + ny;
        swap(s[pos], s[np]);
        if (dfs(depth + 1, np)) { swap(s[pos], s[np]); return true; }
        swap(s[pos], s[np]);
    }
    return false;
}

int main(int argc, char** argv) {
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        string row, all;
        for (int i = 0; i < 5; i++) { cin >> row; all += row; }
        memcpy(s, all.c_str(), 25);
        s[25] = 0;
        int pos = (int)all.find('*');
        int ans = -1;
        for (limitDepth = 0; limitDepth <= 15; limitDepth++)      // ★ 迭代加深
            if (dfs(0, pos)) { ans = limitDepth; break; }
        cout << ans << "\n";
    }
    if (argc > 1 && string(argv[1]) == "count") cerr << "nodes=" << nodes << "\n";
    return 0;
}

// P2324 的**错法**：估价函数**把空位那一格也算了进去**。
//
// 题目：5 × 5 棋盘，12 个白骑士（0）、12 个黑骑士（1）、一个空位（*）。
//       每步把**任意一个骑士按马的走法跳到空位上**（等价于「空位按马的走法挪一格」）。
//       问最少几步能变成目标棋盘；**15 步以内**给不出就输出 -1。
//
// 只差一个条件：`if (s[i] != TARGET[i]) c++;`（少了 `s[i] != '*' &&`）。
//
// ★★★ 而这一个字的后果，是把 IDA* 的地基抽掉了：
//   估价函数必须是**下界**（估出来的步数不能比真实的多），这样「`已走 + h > 上限` 就回头」
//   才不会误伤正确答案。空位算进去之后 h 可能**比真实步数大 1**，
//   于是它会把**正解那条路也剪掉**。
//
// ⚠⚠ 它的错法方向很有欺骗性：**答案不是偏小，是偏大或者干脆变成 -1**
//   （搜不到就往下一个深度试，试到 15 还找不到就报 -1）。
//   ★ 官方样例第一组它就给 **8**（正确答案 7）—— **这一次样例挡住了**。
//   ⚠ 而更有意思的是它**比正解还快**（样例上 7221 个节点 vs 正解 26629）——
//     剪过头的程序总是更快，这正是第 16 章第 8 步说的那件事。
//   ⇒ 页面第 ④ 步把「它的 h 到底高估了多少」量成了一个精确的计数。

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

static const char* TARGET = "1111101111"  "00*11"  "00001"  "00000";
static const int DX[8] = {1, 1, -1, -1, 2, 2, -2, -2};
static const int DY[8] = {2, -2, 2, -2, 1, -1, 1, -1};

static char s[26];
static int limitDepth;
static long long nodes = 0;

/** ★ 错法：连空位那一格也算进去了 —— 这会让 h 高估 */
static int hval() {
    int c = 0;
    for (int i = 0; i < 25; i++) if (s[i] != TARGET[i]) c++;   // ★ 错在这里：空位也算了
    return c;
}

static bool dfs(int depth, int pos) {       // pos = 空位在哪
    nodes++;
    int h = hval();
    if (h == 0) return true;
    if (depth + h > limitDepth) return false;      // ★ IDA* 的那一刀
    int x = pos / 5, y = pos % 5;
    for (int t = 0; t < 8; t++) {
        int nx = x + DX[t], ny = y + DY[t];
        if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
        int np = nx * 5 + ny;
        swap(s[pos], s[np]);
        if (dfs(depth + 1, np)) { swap(s[pos], s[np]); return true; }
        swap(s[pos], s[np]);
    }
    return false;
}

int main(int argc, char** argv) {
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        string row, all;
        for (int i = 0; i < 5; i++) { cin >> row; all += row; }
        memcpy(s, all.c_str(), 25);
        s[25] = 0;
        int pos = (int)all.find('*');
        int ans = -1;
        for (limitDepth = 0; limitDepth <= 15; limitDepth++)      // ★ 迭代加深
            if (dfs(0, pos)) { ans = limitDepth; break; }
        cout << ans << "\n";
    }
    if (argc > 1 && string(argv[1]) == "count") cerr << "nodes=" << nodes << "\n";
    return 0;
}

// P2324 对拍生成器：`./p2324Gen <seed> [倒着走几步] [组数]`
//
// 造法：**从目标棋盘倒着随机走 k 步**。骑士的走法是可逆的（空位挪过去再挪回来），
//   所以这样造出来的局面**一定在 k 步以内解得开**，天然是合法输入。
//
// ⚠⚠ 而这里有一个[第 15 章 P1379](/sol/p1379/) 已经踩过的坑，这一页又量了一遍：
//   **「倒着走 k 步」不等于「距离 k」** —— 随机游走会绕回来。
//   页面第 ⑤ 步实测：倒着走 15 步造出来的局面，**真实最优步数平均只有 8.65 步**（P1379）
//   这道题上是另一个数，但方向一样。
//   ⇒ 想要「难的数据」，光把 k 调大没用，得**把造出来的局面按真实距离筛一遍**。

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

static const char* TARGET = "1111101111"  "00*11"  "00001"  "00000";
static const int DX[8] = {1, 1, -1, -1, 2, 2, -2, -2};
static const int DY[8] = {2, -2, 2, -2, 1, -1, 1, -1};

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int steps = argc > 2 ? atoi(argv[2]) : 12;
    int T = argc > 3 ? atoi(argv[3]) : 1;
    mt19937 rng(seed * 2654435761u + 29u);
    T = max(1, min(10, T));

    printf("%d\n", T);
    for (int t = 0; t < T; t++) {
        string s = TARGET;
        int pos = (int)s.find('*');
        for (int i = 0; i < steps; i++) {
            int cand[8], c = 0, x = pos / 5, y = pos % 5;
            for (int d = 0; d < 8; d++) {
                int nx = x + DX[d], ny = y + DY[d];
                if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
                cand[c++] = nx * 5 + ny;
            }
            int np = cand[rng() % c];
            swap(s[pos], s[np]);
            pos = np;
        }
        for (int i = 0; i < 5; i++) printf("%.5s\n", s.c_str() + i * 5);
    }
    return 0;
}

// P2324 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p2324Count`      人看的版本
// `./p2324Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 五段：
//   ① 官方样例：三个版本各输出什么、各走多少节点；
//   ② ★ 估价函数值多少钱：IDA* vs 纯迭代加深（后者要带节点上限，不然根本不返回）；
//   ③ ★★★ **估价函数是不是下界** —— 拿 IDA* 算出的真实最优步数 d 逐个比：
//      正确的 h 有没有一次 > d？错法那个 h' 呢？
//   ④ 高估版的抓获率，以及它**比正解还快**（剪过头的程序总是更快）；
//   ⑤ ★★★ 回到[第 15 章 P1379](/sol/p1379/) 那条：**「倒着随机走 k 步」不等于「距离 k」**，
//      在这道题上再量一次。

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

static const char* TARGET = "1111101111"  "00*11"  "00001"  "00000";
static const int DX[8] = {1, 1, -1, -1, 2, 2, -2, -2};
static const int DY[8] = {2, -2, 2, -2, 1, -1, 1, -1};

static char s[26];
static int limitDepth;
static long long nodes, cap_;
static bool blew;

/** mode 0 = 正确的 h（空位不算）／ 1 = 错法（空位也算）／ 2 = 没有估价（纯迭代加深） */
static int hval(int mode) {
    if (mode == 2) return 0;
    int c = 0;
    for (int i = 0; i < 25; i++) {
        if (mode == 0 && s[i] == '*') continue;
        if (s[i] != TARGET[i]) c++;
    }
    return c;
}

static bool dfs(int depth, int pos, int mode) {
    if (cap_ && nodes >= cap_) { blew = true; return false; }
    nodes++;
    int h = hval(mode);
    if (h == 0 && strcmp(s, TARGET) == 0) return true;
    if (depth + h > limitDepth) return false;
    if (mode == 2 && depth >= limitDepth) return false;
    int x = pos / 5, y = pos % 5;
    for (int t = 0; t < 8; t++) {
        int nx = x + DX[t], ny = y + DY[t];
        if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
        int np = nx * 5 + ny;
        swap(s[pos], s[np]);
        bool got = dfs(depth + 1, np, mode);
        swap(s[pos], s[np]);
        if (got) return true;
        if (blew) return false;
    }
    return false;
}

/** 返回答案（-1 = 15 步内做不到；-2 = 撞上节点上限）。 */
static int solve(const string& board, int mode, long long& outNodes, long long cap = 0) {
    memcpy(s, board.c_str(), 25);
    s[25] = 0;
    int pos = (int)board.find('*');
    nodes = 0; cap_ = cap; blew = false;
    int ans = -1;
    for (limitDepth = 0; limitDepth <= 15; limitDepth++) {
        if (dfs(0, pos, mode)) { ans = limitDepth; break; }
        if (blew) { outNodes = nodes; return -2; }
    }
    outNodes = nodes;
    return ans;
}

/** 直接算某个局面的 h（不搜索） */
static int hOf(const string& board, int mode) {
    memcpy(s, board.c_str(), 25);
    s[25] = 0;
    return hval(mode);
}

/** 和 p2324Gen.cpp 逐字一致：从目标态倒着随机走 steps 步 */
static string gen(int seed, int steps) {
    mt19937 rng((unsigned)seed * 2654435761u + 29u);
    string t = TARGET;
    int pos = (int)t.find('*');
    for (int i = 0; i < steps; i++) {
        int cand[8], c = 0, x = pos / 5, y = pos % 5;
        for (int d = 0; d < 8; d++) {
            int nx = x + DX[d], ny = y + DY[d];
            if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
            cand[c++] = nx * 5 + ny;
        }
        int np = cand[rng() % c];
        swap(t[pos], t[np]);
        pos = np;
    }
    return t;
}

static const string S1 = "10110" "01*11" "10111" "01001" "00000";
static const string S2 = "01011" "110*1" "01110" "01010" "00100";

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

    /* ① 官方样例 */
    {
        long long n1, n2, n3, n4;
        int a1 = solve(S1, 0, n1), a2 = solve(S2, 0, n2);
        int b1 = solve(S1, 1, n3), b2 = solve(S2, 1, n4);
        if (!CSV) printf("① 官方样例：正解 %d / %d（%lld + %lld 个节点）｜"
                         "高估版 %d / %d（%lld + %lld 个节点 —— ★ 比正解还少）\n",
                         a1, a2, n1, n2, b1, b2, n3, n4);
        row("sample", {a1, a2, n1, n2, b1, b2, n3, n4});
    }

    /* ② 估价函数值多少钱：IDA* vs 纯迭代加深（带节点上限） */
    {
        if (!CSV) printf("\n② 估价函数值多少钱（节点上限 %lld）\n", CAP);
        vector<long long> out;
        // ⚠ 草稿这里用「倒着走 k 步」造的局面，结果四档真实步数只有 4~6 步 ——
        //   纯迭代加深几百个节点就出来了，**那张表量不到任何东西**。
        //   真正要命的是**答案是 -1 的局面**：它必须把 15 层整棵树搜完才敢下结论。
        const char* NM[3] = {"官方样例 ①（答案 7）", "官方样例 ②（答案 -1）", "倒着走 15 步里最深的一个"};
        string deep = gen(1, 15);
        int bestD = -1;
        for (int seed = 1; seed <= 400; seed++) {
            string b = gen(seed, 15);
            long long nn;
            int d = solve(b, 0, nn);
            if (d > bestD) { bestD = d; deep = b; }
        }
        string BOARDS[3] = {S1, S2, deep};
        for (int i = 0; i < 3; i++) {
            long long na, nb;
            int a = solve(BOARDS[i], 0, na);
            int r = solve(BOARDS[i], 2, nb, CAP);
            out.push_back(a); out.push_back(na); out.push_back(r < -1 ? -1 : nb);
            if (!CSV) printf("  %-24s：真实 %2d 步｜IDA* %lld 个节点｜纯迭代加深 %s\n",
                             NM[i], a, na, r < -1 ? "撞上限 5000 万，跑不完" : (to_string(nb) + " 个节点").c_str());
        }
        row("heur", out);
    }

    /* ③ ★★★ 估价函数是不是下界 */
    {
        int badOk = 0, badOver = 0, overStrict = 0, cases = 0;
        for (int seed = 1; seed <= 400; seed++) {
            string b = gen(seed, 12);
            long long nn;
            int d = solve(b, 0, nn);        // 真实最优步数
            if (d < 0) continue;
            cases++;
            if (hOf(b, 0) > d) badOk++;     // 正确的 h 高估了？（应该永远不会）
            if (hOf(b, 1) > d) badOver++;   // 错法的 h 高估了？
            if (hOf(b, 1) > hOf(b, 0)) overStrict++;
        }
        if (!CSV) printf("\n③ %d 个局面上，估价函数和真实最优步数 d 的关系：\n"
                         "   正确的 h > d 的有 %d 个（必须是 0，否则 IDA* 的地基就塌了）\n"
                         "   错法的 h' > d 的有 %d 个｜h' 严格大于 h 的有 %d 个\n",
                         cases, badOk, badOver, overStrict);
        row("admissible", {cases, badOk, badOver, overStrict});
    }

    /* ④ 高估版的抓获率 ＋ 它比正解快多少 */
    {
        if (!CSV) printf("\n④ 高估版：400 个局面里答案不同的有几个（按倒着走的步数分档）\n");
        vector<long long> out;
        for (int k : {6, 9, 12, 15}) {
            int diff = 0;
            long long totOk = 0, totBad = 0;
            for (int seed = 1; seed <= 400; seed++) {
                string b = gen(seed, k);
                long long na, nb;
                int a = solve(b, 0, na), c = solve(b, 1, nb);
                if (a != c) diff++;
                totOk += na; totBad += nb;
            }
            out.push_back(diff);
            if (!CSV) printf("  倒着走 %2d 步：答案不同 %3d / 400｜节点数合计 正解 %lld、高估版 %lld（%.2f 倍）\n",
                             k, diff, totOk, totBad, totBad * 1.0 / totOk);
        }
        row("overCatch", out);
    }

    /* ⑤ ★★★ 「倒着走 k 步」不等于「距离 k」 */
    {
        if (!CSV) printf("\n⑤ 「倒着随机走 k 步」造出来的局面，真实最优步数是多少（每档 400 个，×100）\n");
        vector<long long> out;
        for (int k : {6, 9, 12, 15}) {
            long long sum = 0;
            int cnt = 0, mx = 0;
            for (int seed = 1; seed <= 400; seed++) {
                string b = gen(seed, k);
                long long nn;
                int d = solve(b, 0, nn);
                if (d < 0) continue;
                sum += d; cnt++; mx = max(mx, d);
            }
            out.push_back(sum * 100 / cnt); out.push_back(mx);
            if (!CSV) printf("  倒着走 %2d 步：真实最优平均 %.2f 步，最大 %d 步\n", k, sum * 1.0 / cnt, mx);
        }
        row("walkDist", out);
    }
    return 0;
}