洛谷 P1443 马的遍历

// P1443 马的遍历 —— 能 AC 的那一版
//
// BFS 求最短步数，和本章正文那份 fast.cpp 是同一件事，只差**方向数组**：
//   本章正文：四个方向（上下左右）
//   这道题  ：★ **马走日的八个方向** —— 十六个手抄的数字
//
//     {1,2} {1,-2} {-1,2} {-1,-2} {2,1} {2,-1} {-2,1} {-2,-1}
//
// ⚠ 这一页整页都在说那十六个数字：**它是一个可以穷举的 bug 空间**
//   （8 个方向 × 2 个分量 × 改成另外 3 个值 = 48 个变体，p1443Dirs.cpp 一个不落地跑完）。
//
// 两条一定要记住的：
//   ① **标记要在入队时打，不是出队时** —— 出队才标记会让同一格被反复入队（第 ④ 步量了倍数）；
//   ② 到不了的格子输出 **-1**（`n = 1` 或 `m = 1` 时马根本动不了；样例 3×3 的正中间也是 -1）。

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

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 int n, m, sx, sy;
static int dist_[405][405];
static int qx[160005], qy[160005];

int main() {
    if (scanf("%d %d %d %d", &n, &m, &sx, &sy) != 4) return 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) dist_[i][j] = -1;

    int head = 0, tail = 0;
    dist_[sx][sy] = 0;
    qx[tail] = sx; qy[tail] = sy; tail++;
    while (head < tail) {
        int x = qx[head], y = qy[head]; head++;
        for (int d = 0; d < 8; d++) {
            int nx = x + DX[d], ny = y + DY[d];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (dist_[nx][ny] != -1) continue;
            dist_[nx][ny] = dist_[x][y] + 1;      // ★ 入队时就把距离写死（等于标记）
            qx[tail] = nx; qy[tail] = ny; tail++;
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            printf("%d%c", dist_[i][j], j == m ? '\n' : ' ');
    return 0;
}

// P1443 ⚠ 错法：**方向数组抄错了一个数字**
//
// 和 p1443.cpp 只差一个负号：最后一个方向 `{-2,-1}` 写成了 `{-2, 1}`。
//
//     正确  DY[8] = {2, -2, 2, -2, 1, -1, 1, -1};
//     这里  DY[8] = {2, -2, 2, -2, 1, -1, 1,  1};
//                                          ↑ 少了一个负号
//
// ⇒ `{-2,1}` 于是出现了两次，等于**整个 `{-2,-1}` 方向没了**（马少了一条腿）。
//
// ★★★ 它**过得了官方样例**（3 × 3、起点在左上角）——
//   那么小的棋盘、起点又在角上，往左上方向走的那几条腿根本用不着。
//   p1443Count.cpp 把这件事量成了一张表：48 种「抄错一个数字」里，
//   3 × 3 放过去 14 种，而 **5 × 5 就一个不剩**。

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

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};   // ⚠ 最后那个应该是 -1

static int n, m, sx, sy;
static int dist_[405][405];
static int qx[160005], qy[160005];

int main() {
    if (scanf("%d %d %d %d", &n, &m, &sx, &sy) != 4) return 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) dist_[i][j] = -1;

    int head = 0, tail = 0;
    dist_[sx][sy] = 0;
    qx[tail] = sx; qy[tail] = sy; tail++;
    while (head < tail) {
        int x = qx[head], y = qy[head]; head++;
        for (int d = 0; d < 8; d++) {
            int nx = x + DX[d], ny = y + DY[d];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (dist_[nx][ny] != -1) continue;
            dist_[nx][ny] = dist_[x][y] + 1;
            qx[tail] = nx; qy[tail] = ny; tail++;
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            printf("%d%c", dist_[i][j], j == m ? '\n' : ' ');
    return 0;
}

// P1443 ⚠ 错法：**出队的时候才标记**
//
// 「先把邻居都塞进队列，等轮到它出队再看要不要处理」—— 这个写法看着也说得通。
// ★ 而且它的**答案是对的**，靠的是出队后那一句 `if (vis[x][y]) continue;`：
//   同一个格子第一次出队时距离最小（BFS 层序），后面那几次直接被挡掉。
//
// ⚠ 它的代价在**入队次数**上：一个格子会被它**每一个已经出过队的邻居**各塞一次。
//   p1443Count.cpp 第 ② 段量出来的（400 × 400、起点左上角，一共 160000 格）：
//       入队时标记（p1443.cpp）  160000 次
//       出队才标记（这一版）     635209 次   —— **3.97 倍**
//   ⚠ 注意不是「8 倍」：边上的格子邻居不满八个，而且**只有已经出过队的邻居才会塞它**。
//     ⇒ 「大概是 8nm」这种数是**推出来的**，写进正文之前得跑一遍。
//
// ★ 这一版**能 AC**（3.97 倍换不来 TLE），它是那类「**只坏复杂度、不坏答案**」的写法
//   （第 53 章那条）—— **对拍一个字都说不出来**：p1443Gen.cpp 300 轮，它一次都不会被抓到。
//
// ⚠⚠ 而把那一句守卫去掉会怎样？草稿里写的是「答案就真的错了」——
//   **实测把这句打回来了**，见 p1443LateBad.cpp。

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

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 int n, m, sx, sy;
static int dist_[405][405];
static bool vis[405][405];
/** ⚠ 队列得开大：顶格实测 635209 次入队，这里留了一倍余量 */
static const int QCAP = 1300000;
static int qx[QCAP + 5], qy[QCAP + 5], qd[QCAP + 5];

int main() {
    if (scanf("%d %d %d %d", &n, &m, &sx, &sy) != 4) return 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) dist_[i][j] = -1;

    int head = 0, tail = 0;
    qx[tail] = sx; qy[tail] = sy; qd[tail] = 0; tail++;
    while (head < tail) {
        int x = qx[head], y = qy[head], d0 = qd[head]; head++;
        if (vis[x][y]) continue;                    // ★ 就是这一句在保答案
        vis[x][y] = true;
        dist_[x][y] = d0;
        for (int d = 0; d < 8; d++) {
            int nx = x + DX[d], ny = y + DY[d];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (vis[nx][ny]) continue;
            if (tail >= QCAP) {                     // ⚠ 装不下就喊出来，绝不悄悄少做一步
                fprintf(stderr, "队列装不下：入队次数超过 %d\n", QCAP);
                return 1;
            }
            qx[tail] = nx; qy[tail] = ny; qd[tail] = d0 + 1; tail++;
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            printf("%d%c", dist_[i][j], j == m ? '\n' : ' ');
    return 0;
}

// P1443 ⚠⚠ 错法：出队才标记，**而且少了那一句守卫**
//
// 和 p1443Late.cpp 只差一行：出队之后那句 `if (vis[x][y]) continue;` 没了。
//
// ⚠⚠ 草稿里给这一版写的判词是「答案真的错了」——**实测把它打回来了**：
//   p1443Count.cpp 第 ④ 段把 n, m ≤ 14 的**每一个起点**都比了一遍，
//   **11025 组里 0 组不一致**。
//
// ★ 为什么错不了：**马每走一步必定换一次格子颜色**（黑 ↔ 白）——
//   那张图是**二分图**，同一层的两个格子之间不可能有边。
//   ⇒ 队列里一个格子的所有副本**距离都相同**，写几次都写同一个数，答案坏不了。
//   ⚠ 这不是「这个写法没问题」，是「**这道题的图刚好救了它**」：
//     把方向换成八连通（第 13 章 P1596 那种，有奇环），同一个写法 **n = 2 起就给错答案**。
//
// ⇒ 它真正的代价不是 WA，是**入队次数根本装不下**（p1443Count.cpp 第 ③ 段）：
//       8 × 8  （  64 格）          691 次
//      16 × 16 （ 256 格）      129 861 次
//      24 × 24 （ 576 格）   10 373 317 次   —— 每格一万八
//      32 × 32 （1024 格）   超过 2 × 10⁷，掐掉
//   ⇒ 顶格 400 × 400 上它是 **MLE / TLE**，不是 WA。
//
// ⚠ 所以这一版必须自带一道闸：装不下就**报错退出**，绝不像草稿那样悄悄少入几次队
//   （那样它会打印出一份「看着挺像样」的错答案，而错因根本不在算法上）。

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

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 const long long QCAP = 20000000;             // 2 × 10⁷ 次入队就当「装不下」

static int n, m, sx, sy;
static int dist_[405][405];
static bool vis[405][405];

int main() {
    if (scanf("%d %d %d %d", &n, &m, &sx, &sy) != 4) return 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) dist_[i][j] = -1;

    vector<pair<int, int>> q;                       // (格子编号, 距离)
    q.push_back({(sx - 1) * m + (sy - 1), 0});
    for (size_t h = 0; h < q.size(); h++) {
        int id = q[h].first, d0 = q[h].second;
        int x = id / m + 1, y = id % m + 1;
        vis[x][y] = true;                           // ⚠⚠ 少了 if (vis[x][y]) continue;
        dist_[x][y] = d0;
        for (int d = 0; d < 8; d++) {
            int nx = x + DX[d], ny = y + DY[d];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (vis[nx][ny]) continue;
            if ((long long)q.size() >= QCAP) {
                fprintf(stderr, "队列装不下：入队次数超过 %lld（n = %d, m = %d）\n", QCAP, n, m);
                return 1;
            }
            q.push_back({(nx - 1) * m + (ny - 1), d0 + 1});
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            printf("%d%c", dist_[i][j], j == m ? '\n' : ' ');
    return 0;
}

// P1443 对拍生成器：`./p1443Gen <seed> [maxN]`
//
// 输出就是这道题的一行输入：`n m x y`。
//
// ⚠ `maxN` 默认 **12**，不是题面的 400 —— 这一档是被 p1443LateBad.cpp 逼出来的：
//   那一版少了守卫，入队次数在 24 × 24 就到一千万、32 × 32 装不下（p1443Count.cpp 第 ③ 段）。
//   ⇒ **能把四个版本一起放进对拍的规模，正好只有这么大。**
//   而这恰恰是这一页要说的事：对拍在这道题上**看不见**那两个「标记时机」的错法
//   （它们答案全对），它只抓得到方向数组抄错的那一类。
//
// ★ 另一档 `maxN = 3` 用来复现「官方样例那么大的数据什么都查不出来」。

#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]) : 12;
    if (maxN < 1) maxN = 1;
    mt19937 rng(seed);
    int n = (int)(rng() % (unsigned)maxN) + 1;
    int m = (int)(rng() % (unsigned)maxN) + 1;
    int x = (int)(rng() % (unsigned)n) + 1;
    int y = (int)(rng() % (unsigned)m) + 1;
    printf("%d %d %d %d\n", n, m, x, y);
    return 0;
}

// ★★★ P1443 的度量程序：把三件「猜不得的事」全量出来
//
// 用法：./p1443Count          人话版
//       ./p1443Count csv      给 check:viz 用
//
// ① **方向数组抄错**是一个可以**数完**的 bug 空间：
//    马走日的八个方向是十六个手抄的数字
//        {1,2} {1,-2} {-1,2} {-1,-2} {2,1} {2,-1} {-2,1} {-2,-1}
//    「抄错一个数字」总共只有 8 个方向 × 2 个分量 × 改成另外 3 个值 = **48** 种。
//    ⇒ 一个不落地全跑一遍，看**多大的棋盘才抓得干净** —— 这比对拍便宜得多。
//
// ② 「入队时标记」和「出队才标记」的**入队次数**差多少（n = m = 400）。
//
// ③ 「出队才标记、又少了那句守卫」那一版（p1443LateBad.cpp）：
//    ⚠⚠ 草案里写的是「它答案真的错」—— **实测把这句打回来了**。
//    在马的图上它 11025 组数据一次都没错；错不了的原因是**马每走一步必换格子颜色**
//    （黑↔白），⇒ 那张图是**二分图**，同一层的两个格子之间没有边，
//    于是队列里永远不会出现「距离更大的那份」把答案改坏。
//    它真正的代价在**入队次数**上：那不是「多几倍」，是**装不下**。
//    ★ 而把方向换成八连通（第 13 章 P1596 那种，有奇环 ⇒ 不是二分图），
//      同一个写法 n = 2 起就给错答案 —— 见第 ⑤ 段。

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

static const int CDX[8] = {1, 1, -1, -1, 2, 2, -2, -2};
static const int CDY[8] = {2, -2, 2, -2, 1, -1, 1, -1};
/** 八连通（上下左右 + 四个斜角）—— 有奇环，不是二分图 */
static const int EDX[8] = {1, 1, 1, 0, 0, -1, -1, -1};
static const int EDY[8] = {1, 0, -1, 1, -1, 1, 0, -1};
static int DX[8], DY[8];

/** 正常 BFS（入队时标记）；返回距离矩阵，enq 里带回入队次数 */
static vector<int> bfs(int n, int m, int sx, int sy, const int* dx, const int* dy, long long* enq) {
    vector<int> d((size_t)n * m, -1);
    vector<int> q;
    q.reserve((size_t)n * m);
    d[(size_t)(sx - 1) * m + (sy - 1)] = 0;
    q.push_back((sx - 1) * m + (sy - 1));
    long long pushes = 1;
    for (size_t h = 0; h < q.size(); h++) {
        int x = q[h] / m + 1, y = q[h] % m + 1;
        for (int k = 0; k < 8; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            size_t id = (size_t)(nx - 1) * m + (ny - 1);
            if (d[id] != -1) continue;
            d[id] = d[(size_t)(x - 1) * m + (y - 1)] + 1;
            q.push_back((int)id);
            pushes++;
        }
    }
    if (enq) *enq = pushes;
    return d;
}

/**
 * 出队才标记。
 *   guard = true ：出队后那句 `if (vis) continue;` 还在
 *   guard = false：那句没了
 * ⚠ 没守卫时入队次数会炸 ⇒ 必须给一个上限 cap：
 *   超了就返回空 vector（表示「这一档量不出来」），enq 带回 -1。
 */
static vector<int> bfsLate(int n, int m, int sx, int sy, const int* dx, const int* dy,
                           bool guard, long long cap, long long* enq) {
    vector<int> d((size_t)n * m, -1);
    vector<char> vis((size_t)n * m, 0);
    vector<pair<int, int>> q;                       // (格子, 距离)
    q.push_back({(sx - 1) * m + (sy - 1), 0});
    long long pushes = 1;
    for (size_t h = 0; h < q.size(); h++) {
        int id = q[h].first, d0 = q[h].second;
        if (guard && vis[id]) continue;
        vis[id] = 1;
        d[id] = d0;
        int x = id / m + 1, y = id % m + 1;
        for (int k = 0; k < 8; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            size_t nid = (size_t)(nx - 1) * m + (ny - 1);
            if (vis[nid]) continue;
            q.push_back({(int)nid, d0 + 1});
            if (++pushes > cap) { if (enq) *enq = -1; return {}; }
        }
    }
    if (enq) *enq = pushes;
    return d;
}

/** 48 个变体里，在 n × n、起点 (sx,sy) 上被抓到几个 */
static int caughtAt(int n, int sx, int sy) {
    int c = 0;
    memcpy(DX, CDX, sizeof DX);
    memcpy(DY, CDY, sizeof DY);
    for (int k = 0; k < 8; k++)
        for (int comp = 0; comp < 2; comp++)
            for (int v : {-2, -1, 1, 2}) {
                int* a = comp == 0 ? DX : DY;
                int old = a[k];
                if (v == old) continue;
                a[k] = v;
                long long t;
                if (bfs(n, n, sx, sy, DX, DY, &t) != bfs(n, n, sx, sy, CDX, CDY, &t)) c++;
                a[k] = old;
            }
    return c;
}

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");
    const long long CAP = 20000000;                 // 2 × 10⁷ 次就当「装不下」（和 p1443LateBad.cpp 那道闸同一个数）
    long long t;

    /* ① 48 个变体 × 棋盘边长：多大才抓得干净 */
    int corner[7], center[7];
    for (int n = 3; n <= 9; n++) {
        corner[n - 3] = caughtAt(n, 1, 1);
        center[n - 3] = caughtAt(n, (n + 1) / 2, (n + 1) / 2);
    }
    int firstCleanCorner = 0, firstCleanCenter = 0;
    for (int i = 0; i < 7; i++) {
        if (!firstCleanCorner && corner[i] == 48) firstCleanCorner = i + 3;
        if (!firstCleanCenter && center[i] == 48) firstCleanCenter = i + 3;
    }
    /* 官方样例（3 × 3、起点角上）放过去、而 8 × 8 抓得到的有几个 */
    int onlyBig = corner[5] - corner[0];

    /* 那些漏网的变体，出在哪几个方向上（3 × 3、起点角上） */
    string leakDirs;
    memcpy(DX, CDX, sizeof DX);
    memcpy(DY, CDY, sizeof DY);
    for (int k = 0; k < 8; k++) {
        bool leak = false;
        for (int comp = 0; comp < 2 && !leak; comp++)
            for (int v : {-2, -1, 1, 2}) {
                int* a = comp == 0 ? DX : DY;
                int old2 = a[k];
                if (v == old2) continue;
                a[k] = v;
                long long tt;
                if (bfs(3, 3, 1, 1, DX, DY, &tt) == bfs(3, 3, 1, 1, CDX, CDY, &tt)) leak = true;
                a[k] = old2;
                if (leak) break;
            }
        if (leak) leakDirs += (leakDirs.empty() ? "" : " ") + string("{")
            + to_string(CDX[k]) + "," + to_string(CDY[k]) + "}";
    }

    /* ② 入队次数（n = m = 400，起点左上角，格子一共 160000 个） */
    long long e0 = 0, e1 = 0;
    bfs(400, 400, 1, 1, CDX, CDY, &e0);
    bfsLate(400, 400, 1, 1, CDX, CDY, true, (long long)4e9, &e1);

    /* ③ 「少了守卫」那一版的入队次数：不是多几倍，是装不下 */
    const int BADN[4] = {8, 16, 24, 32};
    long long badEnq[4];
    for (int i = 0; i < 4; i++) bfsLate(BADN[i], BADN[i], 1, 1, CDX, CDY, false, CAP, &badEnq[i]);

    /* ④ ⚠ 而它的**答案**在这道题上一次都没错：n, m ≤ 14 的每一个起点全比一遍 */
    int groups = 0, badAns = 0;
    for (int n = 1; n <= 14; n++)
        for (int m = 1; m <= 14; m++)
            for (int sx = 1; sx <= n; sx++)
                for (int sy = 1; sy <= m; sy++) {
                    groups++;
                    if (bfs(n, m, sx, sy, CDX, CDY, &t)
                        != bfsLate(n, m, sx, sy, CDX, CDY, false, CAP, &t)) badAns++;
                }

    /* ⑤ 反证：同一个写法，方向换成八连通（有奇环 ⇒ 不是二分图）就立刻错 */
    int firstEight = 0;
    for (int n = 2; n <= 12 && !firstEight; n++)
        if (bfs(n, n, 1, 1, EDX, EDY, &t) != bfsLate(n, n, 1, 1, EDX, EDY, false, CAP, &t))
            firstEight = n;
    auto row0 = [](const vector<int>& d, int m) {
        string s;
        for (int j = 0; j < m; j++) s += (j ? " " : "") + to_string(d[j]);
        return s;
    };
    string eOk = row0(bfs(4, 4, 1, 1, EDX, EDY, &t), 4);
    string eBad = row0(bfsLate(4, 4, 1, 1, EDX, EDY, false, CAP, &t), 4);

    if (csv) {
        printf("corner");
        for (int i = 0; i < 7; i++) printf(",%d", corner[i]);
        printf("\ncenter");
        for (int i = 0; i < 7; i++) printf(",%d", center[i]);
        printf("\nvariants,48\nonlyBig,%d\nleakDirs,%s\n", onlyBig, leakDirs.c_str());
        printf("firstCleanCorner,%d\nfirstCleanCenter,%d\n", firstCleanCorner, firstCleanCenter);
        printf("enqEarly,%lld\nenqLate,%lld\nlateRatio100,%lld\n", e0, e1, e1 * 100 / e0);
        for (int i = 0; i < 4; i++) printf("bad%d,%lld\n", BADN[i], badEnq[i]);
        printf("cap,%lld\n", CAP);
        printf("groups,%d\nbadAns,%d\n", groups, badAns);
        printf("firstEight,%d\neightOk,%s\neightBad,%s\n", firstEight, eOk.c_str(), eBad.c_str());
        return 0;
    }

    printf("① 方向数组是十六个手抄的数字 ——「抄错一个」总共只有 48 种，全跑一遍：\n\n");
    printf("   棋盘边长      3    4    5    6    7    8    9\n");
    printf("   起点在角上 ");
    for (int i = 0; i < 7; i++) printf(" %3d ", corner[i]);
    printf("   ← 官方样例就是 3 × 3、起点 (1,1)\n");
    printf("   起点在正中 ");
    for (int i = 0; i < 7; i++) printf(" %3d ", center[i]);
    printf("\n\n");
    printf("   ⇒ 官方样例放过去、8 × 8 抓得到的：%d 种\n", onlyBig);
    printf("     它们全出在这几个方向上：%s\n", leakDirs.c_str());
    printf("   ⇒ 把样例换成 %d × %d（起点角上）／ %d × %d（起点正中），48 种一个不剩\n\n",
           firstCleanCorner, firstCleanCorner, firstCleanCenter, firstCleanCenter);

    printf("② 入队次数（n = m = 400，起点左上角，格子一共 160000 个）：\n");
    printf("   入队时标记（正解）        %9lld 次\n", e0);
    printf("   出队才标记（带守卫）      %9lld 次   —— %.2f 倍\n\n", e1, (double)e1 / (double)e0);

    printf("③ 把那句守卫也去掉，入队次数不是「多几倍」，是**装不下**：\n");
    for (int i = 0; i < 4; i++) {
        printf("   %2d × %-2d（%4d 格）  ", BADN[i], BADN[i], BADN[i] * BADN[i]);
        if (badEnq[i] < 0) printf("超过 %lld 次，掐掉\n", CAP);
        else printf("%12lld 次   —— 每格 %.0f 次\n", badEnq[i], (double)badEnq[i] / (BADN[i] * BADN[i]));
    }

    printf("\n④ ⚠ 可是它的**答案**呢？n, m <= 14 的每一个起点全比一遍：\n");
    printf("   %d 组里和正解不一致的：**%d 组**\n", groups, badAns);
    printf("   ⇒ 「少了守卫就会 WA」这句话在这道题上是**错的** —— 马每走一步必换格子颜色，\n");
    printf("      那张图是二分图，同一层之间没有边。\n\n");

    printf("⑤ 反证：方向换成八连通（有奇环 ⇒ 不是二分图），同一个写法立刻错：\n");
    printf("   n = %d 起就和正解不一致；4 × 4 的第一行：\n", firstEight);
    printf("     正解    %s\n     少守卫  %s\n", eOk.c_str(), eBad.c_str());
    return 0;
}