洛谷 P1747 好奇怪的游戏

// ★ 第一版：照题单的注解「两个起点各跑一次 BFS」—— 这一版就已经能 AC
//
// 想法最直接：一匹马一次 BFS，从它自己的位置出发，走到 (1,1) 就停。
// 12 个方向（8 个「日」+ 4 个「田」）、下界是 1、棋盘 20 × 20 —— 三处都对，它就是对的。
//
// ⚠ 它唯一「多做」的事是**把同一张 400 格的表算了两遍**：
//   入队 800 次，而从 (1,1) 出发只算一次是 400 次（p1747Count.cpp 第 ④ 段）。
//   ⇒ 2 倍。而这道题一共 400 个格子 —— **2 倍在这里一文不值**。
//   所以 p1747.cpp 换成一次 BFS，理由是「一张表、一个出处，说得清」，**不是快**。

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

const int N = 20;
const int DX[12] = {1, 1, -1, -1, 2, 2, -2, -2,  2,  2, -2, -2};
const int DY[12] = {2, -2, 2, -2, 1, -1, 1, -1,  2, -2,  2, -2};

int bfs(int sx, int sy) {
    static int dist_[N + 1][N + 1];
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) dist_[i][j] = -1;

    queue<pair<int, int>> q;
    dist_[sx][sy] = 0;
    q.push({sx, sy});
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        if (x == 1 && y == 1) return dist_[x][y];    // 第一次碰到 (1,1) 就是最短
        for (int k = 0; k < 12; k++) {
            int a = x + DX[k], b = y + DY[k];
            if (a < 1 || a > N || b < 1 || b > N) continue;
            if (dist_[a][b] != -1) continue;
            dist_[a][b] = dist_[x][y] + 1;
            q.push({a, b});
        }
    }
    return -1;
}

int main() {
    int x1_, y1_, x2_, y2_;
    if (scanf("%d %d %d %d", &x1_, &y1_, &x2_, &y2_) != 4) return 0;
    printf("%d\n%d\n", bfs(x1_, y1_), bfs(x2_, y2_));
    return 0;
}

// ⚠ 错法一：边界的下界写成了 0 —— 于是马可以踩到 x 或 y = 0 的格子
//
// 题面在描述的末尾专门写了一句：
//
//     「注意不能走到 x 或 y 坐标 ≤ 0 的位置。」
//
// 而数组是从下标 0 开始的，写 `if (a < 0 || a > N) continue;` 看着天经地义 ——
// 它挡住了「下标越界」，却**没有挡住题面那条规则**：第 0 行、第 0 列被当成了合法棋盘。
//
// ★★★ 这一版的抓获率是这一页最值钱的数字：**400 个起点里只有 1 个答案会变。**
//   那一个是 **(2,2)**：正确答案 3，这一版给 2 ——
//   因为它可以走 (2,2) →日→ (3,0) →日→ (1,1)，而 (3,0) 的纵坐标是 0。
//   ⇒ 官方样例（12 16 / 18 10）**一个字都说不出来**。
//
// 除了那一句边界判断，其余和 p1747.cpp 逐字相同。

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

const int N = 20;
const int DX[12] = {1, 1, -1, -1, 2, 2, -2, -2,  2,  2, -2, -2};
const int DY[12] = {2, -2, 2, -2, 1, -1, 1, -1,  2, -2,  2, -2};

int main() {
    int x1_, y1_, x2_, y2_;
    if (scanf("%d %d %d %d", &x1_, &y1_, &x2_, &y2_) != 4) return 0;

    static int dist_[N + 1][N + 1];
    for (int i = 0; i <= N; i++)
        for (int j = 0; j <= N; j++) dist_[i][j] = -1;

    queue<pair<int, int>> q;
    dist_[1][1] = 0;
    q.push({1, 1});

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 12; k++) {
            int a = x + DX[k], b = y + DY[k];
            if (a < 0 || a > N || b < 0 || b > N) continue;   // ⚠ 下界写成了 0
            if (dist_[a][b] != -1) continue;
            dist_[a][b] = dist_[x][y] + 1;
            q.push({a, b});
        }
    }

    printf("%d\n%d\n", dist_[x1_][y1_], dist_[x2_][y2_]);
    return 0;
}

// ⚠ 错法二：只写了「日」，把「象走田」漏了
//
// 这道题和第 14 章题单上一道 P1443（马的遍历）只差一句话：
// **「马可以走『日』，也可以像象走『田』」** —— 方向从 8 个变成 12 个。
// 把 P1443 那份直接搬过来，漏掉的就是后面那 4 个 (±2, ±2)。
//
// ★ 好消息：**官方样例当场就挡住它** —— 第一行应该是 8，它给 10。
//   （p1747Count.cpp 第 ③ 段：400 个起点里 262 个答案变大，最多多 4 步。）
//
// ⚠ 但它顺带带来一件**和 P1443 完全相反**的事，见 p1747Late.cpp 文件头：
//   「田」走一步**不换格子颜色**，而「日」换 —— 少了这 4 个方向，这张图就是二分图；
//   加上它们，就有奇环了。

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

const int N = 20;
const int DX[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int DY[8] = {2, -2, 2, -2, 1, -1, 1, -1};

int main() {
    int x1_, y1_, x2_, y2_;
    if (scanf("%d %d %d %d", &x1_, &y1_, &x2_, &y2_) != 4) return 0;

    static int dist_[N + 1][N + 1];
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) dist_[i][j] = -1;

    queue<pair<int, int>> q;
    dist_[1][1] = 0;
    q.push({1, 1});

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 8; k++) {              // ⚠ 只有 8 个方向
            int a = x + DX[k], b = y + DY[k];
            if (a < 1 || a > N || b < 1 || b > N) continue;
            if (dist_[a][b] != -1) continue;
            dist_[a][b] = dist_[x][y] + 1;
            q.push({a, b});
        }
    }

    printf("%d\n%d\n", dist_[x1_][y1_], dist_[x2_][y2_]);
    return 0;
}

// ⚠⚠ 错法三：出队才标记，而且少了那句守卫
//
// 这一份是**照抄** [P1443](/sol/p1443/) 里的 `p1443LateBad.cpp`：
// 标记不是在入队时打，而是等它出队才打，并且**没有** `if (vis[x][y]) continue;` 那句守卫。
//
// ★★★ 上一页给那份写法的判词是：「**它答案全对**，代价只在入队次数上」——
//   `n, m ≤ 14` 的 11025 组一次都没错。原因是**马每跳一步必换格子颜色 ⇒ 那是二分图**，
//   队列里同一个格子的所有副本距离都相同，写几遍都写同一个数。
//
// ⚠⚠ **这道题把那句判词翻了过来**，而变的只有方向数组：
//   · 「日」走一步换颜色（1 + 2 = 3，奇数）；
//   · 「田」走一步**不换**颜色（2 + 2 = 4，偶数）。
//   ⇒ 12 个方向的这张图**有奇环**：同一个格子既能用奇数步到、也能用偶数步到。
//   于是队列里同一格的副本距离**不一样**，后到的那份把先到的正确值覆盖掉。
//
//   实测（p1747Count.cpp 第 ⑤ 段，同一份代码、同一张棋盘，只换方向数组）：
//
//       12 个方向（有奇环）：错 324 / 400
//        8 个方向（二分图）：错 ★ 0 / 400
//
//   ⇒ **「这个写法会不会 WA」缺一个主语，主语是那张图有没有奇环。**
//
// ⚠ 队列装不下就喊出来，绝不悄悄少入几次队（P1443 那条教训）。

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

const int N = 20;
const int DX[12] = {1, 1, -1, -1, 2, 2, -2, -2,  2,  2, -2, -2};
const int DY[12] = {2, -2, 2, -2, 1, -1, 1, -1,  2, -2,  2, -2};
const long long QCAP = 20000000LL;

int dist_[N + 1][N + 1];
bool vis[N + 1][N + 1];

int main() {
    int x1_, y1_, x2_, y2_;
    if (scanf("%d %d %d %d", &x1_, &y1_, &x2_, &y2_) != 4) return 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) dist_[i][j] = -1;

    // 把 (x, y, d) 压进一个 int：x, y ≤ 20 各占 5 位，d 占剩下的
    vector<int> q;
    q.push_back((1 << 16) | (1 << 8) | 0);
    for (size_t h = 0; h < q.size(); h++) {
        int x = q[h] >> 16, y = (q[h] >> 8) & 255, d0 = q[h] & 255;
        vis[x][y] = true;                 // ⚠⚠ 少了 if (vis[x][y]) continue;
        dist_[x][y] = d0;
        for (int k = 0; k < 12; k++) {
            int a = x + DX[k], b = y + DY[k];
            if (a < 1 || a > N || b < 1 || b > N) continue;
            if (vis[a][b]) continue;
            if ((long long)q.size() >= QCAP) {
                fprintf(stderr, "队列装不下：入队次数超过 %lld\n", QCAP);
                return 1;
            }
            q.push_back((a << 16) | (b << 8) | (d0 + 1));
        }
    }

    printf("%d\n%d\n", dist_[x1_][y1_], dist_[x2_][y2_]);
    return 0;
}

// P1747 好奇怪的游戏 —— BFS（★ 最终版：一次 BFS 就够）
//
// 题目：马既能走「日」（8 个方向），也能像象一样走「田」（4 个方向），一共 12 个方向。
//       两匹马分别在 (x1,y1) 和 (x2,y2)，各自要走到 (1,1)，求最少步数。
//       ⚠ 不能走到 x 或 y ≤ 0 的位置；满足这个限制的 (x,y) 都可以到达。
//
// ★ 为什么一次 BFS 就够（而题单的注解写的是「两个起点各跑一次」）：
//   12 个方向是**成对相反**的（有 (+1,+2) 就有 (-1,-2)，有 (+2,+2) 就有 (-2,-2)），
//   而「x, y ≥ 1」这个限制对两个端点是同一条 —— 于是
//
//       从 (x,y) 走到 (1,1) 的最少步数  ==  从 (1,1) 走到 (x,y) 的最少步数
//
//   ⇒ 从 (1,1) BFS 一次，整张表就出来了，两匹马各查一次。
//   ⚠ 这不是为了快（这道题一共才 400 个格子，两次也就 800 次入队）——
//     是为了**说得清**：一张表、一个出处。
//
// ★ 棋盘开多大？题面只说输入 x, y ≤ 20，**没说棋盘只有 20 × 20**。
//   实测（p1747Count.cpp 第 ② 段）：棋盘开到 20 和开到 400，
//   400 个起点的答案**一个不差** —— 最优路径从来不需要绕到 20 外面去。
//   ⇒ 所以这里就开 20。这是量出来的，不是猜的。

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

const int N = 20;
// 前 8 个是「日」，后 4 个是「田」
const int DX[12] = {1, 1, -1, -1, 2, 2, -2, -2,  2,  2, -2, -2};
const int DY[12] = {2, -2, 2, -2, 1, -1, 1, -1,  2, -2,  2, -2};

int main() {
    int x1_, y1_, x2_, y2_;
    if (scanf("%d %d %d %d", &x1_, &y1_, &x2_, &y2_) != 4) return 0;

    static int dist_[N + 1][N + 1];
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++) dist_[i][j] = -1;

    queue<pair<int, int>> q;
    dist_[1][1] = 0;
    q.push({1, 1});

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < 12; k++) {
            int a = x + DX[k], b = y + DY[k];
            if (a < 1 || a > N || b < 1 || b > N) continue;   // ★ 下界是 1，不是 0
            if (dist_[a][b] != -1) continue;
            dist_[a][b] = dist_[x][y] + 1;                    // 入队时就定下距离
            q.push({a, b});
        }
    }

    printf("%d\n%d\n", dist_[x1_][y1_], dist_[x2_][y2_]);
    return 0;
}

// P1747 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1747Count`      人看的版本
// `./p1747Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// ★ 这道题的**输入空间只有 400 个起点**（x, y ≤ 20），所以这一页**不需要对拍** ——
//   每一段都是把 400 个起点**全跑一遍**，给的是「一个不差」而不是「抓获率」。
//
// 六段：
//   ① 题面那句「不能走到 x 或 y ≤ 0」是**命门**：把下界放宽，400 个里只有 1 个答案变；
//   ② 而「x, y ≤ 20」是**输入范围不是棋盘范围**：棋盘开 20 和开 400，400 个起点一个不差；
//   ③ 漏掉「象走田」：262 个答案变大；
//   ④ 一次 BFS ／ 两次 BFS 的入队次数；
//   ⑤ 出队才标记、少了守卫：同一份写法，只换方向数组，12 个方向错 324 个、8 个方向 0 个；
//   ⑥ 为什么会这样：12 个方向的图**有奇环**（找出最小的那个「奇偶都能到」的格子）。

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

static bool CSV = false;
// 前 8 个是「日」，后 4 个是「田」
static const int DX[12] = {1, 1, -1, -1, 2, 2, -2, -2,  2,  2, -2, -2};
static const int DY[12] = {2, -2, 2, -2, 1, -1, 1, -1,  2, -2,  2, -2};

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

/** 从 (1,1) BFS：坐标允许 lo..hi，方向取前 nd 个。返回 dist（按下标平移到 0 起）。 */
static vector<vector<int>> bfs(int lo, int hi, int nd) {
    int n = hi - lo + 1;
    vector<vector<int>> d(n, vector<int>(n, -1));
    auto id = [&](int v) { return v - lo; };
    queue<pair<int, int>> q;
    d[id(1)][id(1)] = 0;
    q.push({1, 1});
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int k = 0; k < nd; k++) {
            int a = x + DX[k], b = y + DY[k];
            if (a < lo || a > hi || b < lo || b > hi) continue;
            if (d[id(a)][id(b)] != -1) continue;
            d[id(a)][id(b)] = d[id(x)][id(y)] + 1;
            q.push({a, b});
        }
    }
    return d;
}

/** 出队才标记的写法。guard = 是否保留那句 if (vis) continue。返回 (dist, 入队次数)。 */
static pair<vector<vector<int>>, long long> lateRun(int N, int nd, bool guard) {
    vector<vector<int>> d(N + 1, vector<int>(N + 1, -1));
    vector<vector<char>> vis(N + 1, vector<char>(N + 1, 0));
    vector<array<int, 3>> q;
    q.push_back({1, 1, 0});
    long long pushes = 1;
    for (size_t h = 0; h < q.size(); h++) {
        int x = q[h][0], y = q[h][1], d0 = q[h][2];
        if (guard && vis[x][y]) continue;
        vis[x][y] = true;
        d[x][y] = d0;
        for (int k = 0; k < nd; k++) {
            int a = x + DX[k], b = y + DY[k];
            if (a < 1 || a > N || b < 1 || b > N) continue;
            if (vis[a][b]) continue;
            q.push_back({a, b, d0 + 1});
            pushes++;
        }
    }
    return {d, pushes};
}

int main(int argc, char** argv) {
    CSV = (argc > 1 && string(argv[1]) == "csv");
    const int N = 20;
    auto ref = bfs(1, 400, 12);                    // 棋盘足够大 + 下界正确，当作真值
    auto at = [&](const vector<vector<int>>& d, int lo, int x, int y) { return d[x - lo][y - lo]; };

    /* ① 下界放宽（题面那句「不能走到 x 或 y ≤ 0」） */
    {
        vector<long long> changed;
        vector<int> los = {0, -1, -2, -9};
        int firstX = 0, firstY = 0, okv = 0, badv = 0;
        if (!CSV) printf("① 把下界从 1 放宽（题面：不能走到 x 或 y ≤ 0）\n");
        for (int lo : los) {
            auto d = bfs(lo, 400, 12);
            int c = 0;
            for (int x = 1; x <= N; x++)
                for (int y = 1; y <= N; y++)
                    if (at(ref, 1, x, y) != at(d, lo, x, y)) {
                        c++;
                        if (!firstX) { firstX = x; firstY = y; okv = at(ref, 1, x, y); badv = at(d, lo, x, y); }
                    }
            changed.push_back(c);
            if (!CSV) printf("   允许走到 %3d：400 个起点里 %d 个答案变了\n", lo, c);
        }
        if (!CSV) printf("   ★ 唯一变掉的那个是 (%d,%d)：正确 %d，放宽之后 %d\n\n", firstX, firstY, okv, badv);
        row("loosenLo", changed);
        row("onlyPoint", {firstX, firstY, okv, badv});
    }

    /* ② 棋盘上界（题面只说输入 ≤ 20） */
    {
        vector<long long> diffs;
        vector<int> caps = {20, 21, 25, 40, 100};
        int maxAns = 0;
        for (int x = 1; x <= N; x++)
            for (int y = 1; y <= N; y++) maxAns = max(maxAns, at(ref, 1, x, y));
        if (!CSV) printf("② 棋盘开多大够用（真值是开到 400）\n");
        for (int cap : caps) {
            auto d = bfs(1, cap, 12);
            int c = 0;
            for (int x = 1; x <= N; x++)
                for (int y = 1; y <= N; y++)
                    if (at(ref, 1, x, y) != at(d, 1, x, y)) c++;
            diffs.push_back(c);
            if (!CSV) printf("   棋盘 1..%3d：和真值不同的 %d / 400\n", cap, c);
        }
        if (!CSV) printf("   ⇒ 20 × 20 就够；20 × 20 里最大的答案是 %d 步\n\n", maxAns);
        row("capDiff", diffs);
        row("maxAns", {maxAns});
    }

    /* ③ 漏掉「象走田」 */
    {
        auto only8 = bfs(1, 400, 8);
        int c = 0, worst = 0;
        for (int x = 1; x <= N; x++)
            for (int y = 1; y <= N; y++) {
                int a = at(ref, 1, x, y), b = at(only8, 1, x, y);
                if (a != b) { c++; worst = max(worst, b - a); }
            }
        if (!CSV)
            printf("③ 只写「日」漏掉「田」：400 个起点里 %d 个答案变大（最多多 %d 步）；"
                   "样例 (12,16) 由 %d 变成 %d\n\n",
                   c, worst, at(ref, 1, 12, 16), at(only8, 1, 12, 16));
        row("noBishop", {c, worst, at(ref, 1, 12, 16), at(only8, 1, 12, 16)});
    }

    /* ④ 一次 BFS ／ 两次 BFS 的入队次数 */
    {
        // 一次：从 (1,1) 铺满 20 × 20
        long long once = 0;
        {
            vector<vector<int>> d(N + 1, vector<int>(N + 1, -1));
            queue<pair<int, int>> q;
            d[1][1] = 0; q.push({1, 1}); once = 1;
            while (!q.empty()) {
                auto [x, y] = q.front(); q.pop();
                for (int k = 0; k < 12; k++) {
                    int a = x + DX[k], b = y + DY[k];
                    if (a < 1 || a > N || b < 1 || b > N || d[a][b] != -1) continue;
                    d[a][b] = d[x][y] + 1; q.push({a, b}); once++;
                }
            }
        }
        if (!CSV)
            printf("④ 入队次数：一次 BFS（从 (1,1) 铺满）%lld 次；两匹马各跑一次就是 %lld 次\n\n",
                   once, once * 2);
        row("pushOnce", {once, once * 2});
    }

    /* ⑤ 出队才标记：同一份写法，只换方向数组 */
    {
        vector<long long> wrong, pushes;
        if (!CSV) printf("⑤ 出队才标记（同一份写法，只换方向数组和那句守卫）\n");
        for (int nd : {12, 8})
            for (bool guard : {true, false}) {
                auto [d, p] = lateRun(N, nd, guard);
                int c = 0;
                auto good = bfs(1, 400, nd);
                for (int x = 1; x <= N; x++)
                    for (int y = 1; y <= N; y++)
                        if (at(good, 1, x, y) != d[x][y]) c++;
                wrong.push_back(c);
                pushes.push_back(p);
                if (!CSV)
                    printf("   %2d 个方向，%s：错 %3d / 400，入队 %8lld 次\n",
                           nd, guard ? "有守卫" : "没守卫", c, p);
            }
        if (!CSV) printf("   ⇒ 只有「12 个方向 + 没守卫」这一格是错的 —— 主语是那张图有没有奇环\n\n");
        row("lateWrong", wrong);
        row("latePush", pushes);
    }

    /* ⑥ 奇环的证据：某个格子到 (1,1) 既有奇数步也有偶数步的走法 */
    {
        // 状态是 (x, y, 步数奇偶)
        vector<vector<array<int, 2>>> d(N + 1, vector<array<int, 2>>(N + 1, {-1, -1}));
        queue<array<int, 3>> q;
        d[1][1][0] = 0;
        q.push({1, 1, 0});
        while (!q.empty()) {
            auto [x, y, p] = q.front();
            q.pop();
            for (int k = 0; k < 12; k++) {
                int a = x + DX[k], b = y + DY[k], np = p ^ 1;
                if (a < 1 || a > N || b < 1 || b > N) continue;
                if (d[a][b][np] != -1) continue;
                d[a][b][np] = d[x][y][p] + 1;
                q.push({a, b, np});
            }
        }
        int fx = 0, fy = 0, e = 0, o = 0;
        for (int x = 1; x <= N && !fx; x++)
            for (int y = 1; y <= N && !fx; y++)
                if (d[x][y][0] != -1 && d[x][y][1] != -1 && !(x == 1 && y == 1)) {
                    fx = x; fy = y; e = d[x][y][0]; o = d[x][y][1];
                }
        if (!CSV)
            printf("⑥ 有奇环的证据：格子 (%d,%d) 到 (1,1) 既有 %d 步的走法、也有 %d 步的走法\n"
                   "   （「日」换颜色、「田」不换 —— 少了「田」这张图就是二分图了）\n", fx, fy, e, o);
        row("oddCycle", {fx, fy, e, o});
    }
    return 0;
}