洛谷 P1518 [USACO2.4] 两只塔姆沃斯牛

// P1518 的**第一版**：老老实实模拟，**循环十万次**没抓到就当抓不到。
//
// 题目：10 × 10 的地图，`.` 空地、`*` 障碍、`C` 两头牛、`F` 农夫。
//       每分钟：面前那格能走就往前一步，否则**用这一分钟顺时针转 90 度**（地图外也算障碍）。
//       牛和农夫**同时**动，一开始都朝北。某分钟末落在同一格就算抓到，输出用了几分钟；
//       永远抓不到输出 0。
//
// ⚠ 这一版**也能 AC** —— 这一页不打算假装它是错的。
//   它的问题只有一句话：**「十万」是拍出来的，你说不清为什么够。**
//
//   页面第 ③ ④ 步把这句话量成了数字：
//     · 20000 张随机地图上，答案最大只有 **205**，判定「抓不到」最多只要 **572** 步；
//     · 可**专门去找**，答案能到 **506**、判定「抓不到」要 **839** 步。
//     ⇒ **实测最大不是安全上限。** 拍 1000 也许够，拍 300 就错 —— 而你手上没有判据。
//
// ★ 而这道题**有**一个不用拍的判据（见 p1518.cpp）：状态有限 ＋ 过程确定 ⇒ 状态一重复就停。

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

static const int DR[4] = {-1, 0, 1, 0};      // 北 东 南 西 —— 顺时针
static const int DC[4] = {0, 1, 0, -1};

static char g[10][11];

/** 走一分钟：能往前就往前，否则原地顺时针转 90 度。 */
static void step(int& r, int& c, int& d) {
    int nr = r + DR[d], nc = c + DC[d];
    if (nr < 0 || nr >= 10 || nc < 0 || nc >= 10 || g[nr][nc] == '*') { d = (d + 1) % 4; return; }
    r = nr; c = nc;
}

int main(int argc, char** argv) {
    int cr = 0, cc = 0, fr = 0, fc = 0;
    for (int i = 0; i < 10; i++) {
        if (!(cin >> g[i])) return 0;
        for (int j = 0; j < 10; j++) {
            if (g[i][j] == 'C') { cr = i; cc = j; }
            if (g[i][j] == 'F') { fr = i; fc = j; }
        }
    }

    const long long LIMIT = 100000;          // ★ 拍出来的：为什么是十万？说不清
    int cd = 0, fd = 0;
    long long t = 0, steps = 0;
    while (steps < LIMIT) {
        step(cr, cc, cd);
        step(fr, fc, fd);
        steps++;
        if (cr == fr && cc == fc) { t = steps; break; }
    }
    cout << t << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "steps=" << steps << "\n";
    return 0;
}

// P1518 的**错法二**：把「转 90 度**用掉这一分钟**」读成了「转到能走为止，再走一步」。
//
// 题目：10 × 10 的地图，`.` 空地、`*` 障碍、`C` 两头牛、`F` 农夫。
//       每分钟：面前那格能走就往前一步，否则**用这一分钟顺时针转 90 度**（地图外也算障碍）。
//       牛和农夫**同时**动，一开始都朝北。某分钟末落在同一格就算抓到，输出用了几分钟；
//       永远抓不到输出 0。
//
// 题面原话：「如果前方无障碍……它们会按照原来的方向前进一步。**否则它们会用这一分钟
//   顺时针转 90 度**。」—— 转向**本身就是这一分钟做的事**，转完这一分钟就没了。
//
// ⚠ 而「转到能走再走一步」读起来更顺，也更像常识。这一版就是那么写的：
//   它每一分钟都保证走一步，于是**同样的分钟数里走得更远**，答案偏小或者变成 0。
//
// ★ 页面第 ⑤ 步：它在官方样例上就挂了（给的不是 49）—— 这是本页三个错法里最好抓的一个。

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

static const int DR[4] = {-1, 0, 1, 0};      // 北 东 南 西 —— 顺时针
static const int DC[4] = {0, 1, 0, -1};

static char g[10][11];

/** 走一分钟：能往前就往前，否则原地顺时针转 90 度。 */
static void step(int& r, int& c, int& d) {
    for (int t = 0; t < 4; t++) {            // ★ 错在这里：转向不占用这一分钟
        int nr = r + DR[d], nc = c + DC[d];
        if (nr >= 0 && nr < 10 && nc >= 0 && nc < 10 && g[nr][nc] != '*') { r = nr; c = nc; return; }
        d = (d + 1) % 4;
    }
}

int main(int argc, char** argv) {
    int cr = 0, cc = 0, fr = 0, fc = 0;
    for (int i = 0; i < 10; i++) {
        if (!(cin >> g[i])) return 0;
        for (int j = 0; j < 10; j++) {
            if (g[i][j] == 'C') { cr = i; cc = j; }
            if (g[i][j] == 'F') { fr = i; fc = j; }
        }
    }

    static bool vis[100][4][100][4];         // 160000 个 bool，1.6 KB 都不到
    int cd = 0, fd = 0;                      // 都朝北
    long long t = 0, steps = 0;
    while (true) {
        int s1 = cr * 10 + cc, s2 = fr * 10 + fc;
        if (vis[s1][cd][s2][fd]) { t = 0; break; }   // ★ 状态重复 ⇒ 从此循环，永远抓不到
        vis[s1][cd][s2][fd] = true;
        step(cr, cc, cd);
        step(fr, fc, fd);
        steps++;
        if (cr == fr && cc == fc) { t = steps; break; }
    }
    cout << t << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "steps=" << steps << "\n";
    return 0;
}

// P1518 的**错法三**：牛和农夫**不是同时**动 —— 先动牛、立刻比一次，再动农夫、又比一次。
//
// 题目：10 × 10 的地图，`.` 空地、`*` 障碍、`C` 两头牛、`F` 农夫。
//       每分钟：面前那格能走就往前一步，否则**用这一分钟顺时针转 90 度**（地图外也算障碍）。
//       牛和农夫**同时**动，一开始都朝北。某分钟末落在同一格就算抓到，输出用了几分钟；
//       永远抓不到输出 0。
//
// 题面原话：「每次（每分钟）Farmer John 和两头牛的移动是**同时**的。
//   如果他们在移动的时候**穿过对方**，但是没有在同一格相遇，我们**不认为**他们相遇了。」
//
// ⚠ 这句话是题面里唯一一句「反常识」的规定，而顺手写的模拟正好会违反它：
//   一根一根地动、动完就比，等于把「擦肩而过」也算成了抓到。
//
// ★ 我原来以为这个要「两人正好互换格子」才触发，所以会很难抓 —— **实测不是**：
//   它在**官方样例上就挂了**（给 42，正确答案 49）。触发条件比想象宽得多：
//   只要某一分钟「牛走进了农夫**还没离开**的那一格」就够，不必真的互换。
//   ⇒ 又一次「我知道这个 bug 靠什么现形，其实只知道了一半」。

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

static const int DR[4] = {-1, 0, 1, 0};      // 北 东 南 西 —— 顺时针
static const int DC[4] = {0, 1, 0, -1};

static char g[10][11];

/** 走一分钟：能往前就往前，否则原地顺时针转 90 度。 */
static void step(int& r, int& c, int& d) {
    int nr = r + DR[d], nc = c + DC[d];
    if (nr < 0 || nr >= 10 || nc < 0 || nc >= 10 || g[nr][nc] == '*') { d = (d + 1) % 4; return; }
    r = nr; c = nc;
}

int main(int argc, char** argv) {
    int cr = 0, cc = 0, fr = 0, fc = 0;
    for (int i = 0; i < 10; i++) {
        if (!(cin >> g[i])) return 0;
        for (int j = 0; j < 10; j++) {
            if (g[i][j] == 'C') { cr = i; cc = j; }
            if (g[i][j] == 'F') { fr = i; fc = j; }
        }
    }

    static bool vis[100][4][100][4];         // 160000 个 bool，1.6 KB 都不到
    int cd = 0, fd = 0;                      // 都朝北
    long long t = 0, steps = 0;
    while (true) {
        int s1 = cr * 10 + cc, s2 = fr * 10 + fc;
        if (vis[s1][cd][s2][fd]) { t = 0; break; }   // ★ 状态重复 ⇒ 从此循环，永远抓不到
        vis[s1][cd][s2][fd] = true;
        step(cr, cc, cd);
        steps++;
        if (cr == fr && cc == fc) { t = steps; break; }   // ★ 错在这里：农夫还没动就比了
        step(fr, fc, fd);
        if (cr == fr && cc == fc) { t = steps; break; }
    }
    cout << t << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "steps=" << steps << "\n";
    return 0;
}

// P1518 两只塔姆沃斯牛 —— 模拟 ＋ ★ 用「状态重复」判定永不相遇（★ 这一版就能 AC）
//
// 题目：10 × 10 的地图，`.` 空地、`*` 障碍、`C` 两头牛、`F` 农夫。
//       每分钟：面前那格能走就往前一步，否则**用这一分钟顺时针转 90 度**（地图外也算障碍）。
//       牛和农夫**同时**动，一开始都朝北。某分钟末落在同一格就算抓到，输出用了几分钟；
//       永远抓不到输出 0。
//
// 模拟本身没有任何难点 —— 这道题真正要回答的是**另一个问题**：
//
//   ⚠⚠ **「永远抓不到」这件事，你凭什么敢下结论？**
//
// ★★★ 关键的一步：**整个过程是完全确定的，而状态是有限的。**
//   一个状态 =（牛的格子、牛的朝向、农夫的格子、农夫的朝向）
//            = 100 × 4 × 100 × 4 = **160000** 种。
//   下一分钟的状态只由这一分钟的状态决定 ⇒ 一旦某个状态第二次出现，
//   后面就是一模一样的循环，**再走一亿分钟也不会有新事发生**。
//   ⇒ 见到重复状态就可以立刻输出 0，而且这个「立刻」是**证明**，不是猜。
//
// ⚠ 对照：大多数人的第一版是「循环个十万次，没抓到就当抓不到」（p1518Guess.cpp）。
//   那一版**也能 AC** —— 可它说不清「十万」为什么够。页面第 ③ ④ 步量了这件事。

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

static const int DR[4] = {-1, 0, 1, 0};      // 北 东 南 西 —— 顺时针
static const int DC[4] = {0, 1, 0, -1};

static char g[10][11];

/** 走一分钟：能往前就往前，否则原地顺时针转 90 度。 */
static void step(int& r, int& c, int& d) {
    int nr = r + DR[d], nc = c + DC[d];
    if (nr < 0 || nr >= 10 || nc < 0 || nc >= 10 || g[nr][nc] == '*') { d = (d + 1) % 4; return; }
    r = nr; c = nc;
}

int main(int argc, char** argv) {
    int cr = 0, cc = 0, fr = 0, fc = 0;
    for (int i = 0; i < 10; i++) {
        if (!(cin >> g[i])) return 0;
        for (int j = 0; j < 10; j++) {
            if (g[i][j] == 'C') { cr = i; cc = j; }
            if (g[i][j] == 'F') { fr = i; fc = j; }
        }
    }

    static bool vis[100][4][100][4];         // 160000 字节 = 156 KB，随便开
    int cd = 0, fd = 0;                      // 都朝北
    long long t = 0, steps = 0;
    while (true) {
        int s1 = cr * 10 + cc, s2 = fr * 10 + fc;
        if (vis[s1][cd][s2][fd]) { t = 0; break; }   // ★ 状态重复 ⇒ 从此循环，永远抓不到
        vis[s1][cd][s2][fd] = true;
        step(cr, cc, cd);
        step(fr, fc, fd);
        steps++;
        if (cr == fr && cc == fc) { t = steps; break; }
    }
    cout << t << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "steps=" << steps << "\n";
    return 0;
}

// P1518 的**错法一**：和 p1518Guess.cpp 只差一个数字 —— 上限从 100000 拍成了 **300**。
//
// 题目：10 × 10 的地图，`.` 空地、`*` 障碍、`C` 两头牛、`F` 农夫。
//       每分钟：面前那格能走就往前一步，否则**用这一分钟顺时针转 90 度**（地图外也算障碍）。
//       牛和农夫**同时**动，一开始都朝北。某分钟末落在同一格就算抓到，输出用了几分钟；
//       永远抓不到输出 0。
//
// ★★★ 它存在的意义，是把「拍一个上限」这件事的风险变成一个可以量的东西：
//   300 这个数**看起来非常宽裕** —— 20000 张随机地图上答案的中位数只有十几步。
//   可它是错的，而且页面第 ④ 步会告诉你，随机对拍要多少轮才碰得到一次。

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

static const int DR[4] = {-1, 0, 1, 0};      // 北 东 南 西 —— 顺时针
static const int DC[4] = {0, 1, 0, -1};

static char g[10][11];

/** 走一分钟：能往前就往前，否则原地顺时针转 90 度。 */
static void step(int& r, int& c, int& d) {
    int nr = r + DR[d], nc = c + DC[d];
    if (nr < 0 || nr >= 10 || nc < 0 || nc >= 10 || g[nr][nc] == '*') { d = (d + 1) % 4; return; }
    r = nr; c = nc;
}

int main(int argc, char** argv) {
    int cr = 0, cc = 0, fr = 0, fc = 0;
    for (int i = 0; i < 10; i++) {
        if (!(cin >> g[i])) return 0;
        for (int j = 0; j < 10; j++) {
            if (g[i][j] == 'C') { cr = i; cc = j; }
            if (g[i][j] == 'F') { fr = i; fc = j; }
        }
    }

    const long long LIMIT = 300;             // ★ 错在这里：拍小了
    int cd = 0, fd = 0;
    long long t = 0, steps = 0;
    while (steps < LIMIT) {
        step(cr, cc, cd);
        step(fr, fc, fd);
        steps++;
        if (cr == fr && cc == fc) { t = steps; break; }
    }
    cout << t << "\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "steps=" << steps << "\n";
    return 0;
}

// P1518 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1518Count`      人看的版本
// `./p1518Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 六段：
//   ① 官方样例：五个版本各输出什么（★ 两个错法在这一组就挂了）；
//   ② ★★★ 随机地图上的分布：**七成以上的图是「永远抓不到」的**，
//      答案的中位数只有十几步、最大 205，判定「抓不到」最多 572 步；
//   ③ ★★★ 可**专门去找**：爬山搜出来的两张图，答案 506 ／ 判环 839 步 ——
//      ⇒ **实测最大不是安全上限**；
//   ④ ★ 「上限拍多少才够」：把 100000 换成 100 / 200 / 300 / 500 / 1000，各错多少组；
//   ⑤ 三个错法的抓获率 —— ⚠ 并且**剔掉「两版一起输出 0」的轮数**，那些轮验的是零；
//   ⑥ 判重版实际走了多少步：平均和最大。
//
// ⚠ 这里的 vis 用「时间戳」而不是 memset：160000 个格子 memset 十万遍要 16 GB 的写入。

#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 int DR[4] = {-1, 0, 1, 0};
static const int DC[4] = {0, 1, 0, -1};
static char g[10][11];

/* 四种走法：0 正解／Guess（转向占一分钟）、1 Turn（转向不占时间） */
static void stepOk(int& r, int& c, int& d) {
    int nr = r + DR[d], nc = c + DC[d];
    if (nr < 0 || nr >= 10 || nc < 0 || nc >= 10 || g[nr][nc] == '*') { d = (d + 1) % 4; return; }
    r = nr; c = nc;
}
static void stepTurn(int& r, int& c, int& d) {
    for (int t = 0; t < 4; t++) {
        int nr = r + DR[d], nc = c + DC[d];
        if (nr >= 0 && nr < 10 && nc >= 0 && nc < 10 && g[nr][nc] != '*') { r = nr; c = nc; return; }
        d = (d + 1) % 4;
    }
}

static int vis[100][4][100][4];
static int stamp_ = 0;

enum Kind { OK, GUESS, TURN, CROSS };

/** 返回答案；steps 里放实际走的分钟数。limit 只对 GUESS 那一类有意义。 */
static long long solve(int cr, int cc, int fr, int fc, Kind k, long long limit, long long& steps) {
    void (*mv)(int&, int&, int&) = (k == TURN) ? stepTurn : stepOk;
    int cd = 0, fd = 0;
    steps = 0;
    if (k == OK) {
        stamp_++;
        while (true) {
            int a = cr * 10 + cc, b = fr * 10 + fc;
            if (vis[a][cd][b][fd] == stamp_) return 0;
            vis[a][cd][b][fd] = stamp_;
            mv(cr, cc, cd); mv(fr, fc, fd);
            steps++;
            if (cr == fr && cc == fc) return steps;
        }
    }
    while (steps < limit) {
        mv(cr, cc, cd);
        steps++;
        if (k == CROSS && cr == fr && cc == fc) return steps;   // ★ 顺序移动那个错法
        mv(fr, fc, fd);
        if (cr == fr && cc == fc) return steps;
    }
    return 0;
}

/** 按 seed 和密度造一张图（和 p1518Gen.cpp 逐字一致），起点写进 cr/cc/fr/fc。 */
static void gen(int seed, int forcePct, int& cr, int& cc, int& fr, int& fc) {
    mt19937 rng((unsigned)seed * 2654435761u + 11u);
    int pct = forcePct > 0 ? forcePct : (int)(rng() % 36 + 5);
    if (forcePct > 0) rng();                       // ⚠ 和生成器对齐：不取密度时那一次调用也要走掉
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) g[i][j] = ((int)(rng() % 100) < pct) ? '*' : '.';
        g[i][10] = 0;
    }
    do { cr = rng() % 10; cc = rng() % 10; } while (g[cr][cc] == '*');
    do { fr = rng() % 10; fc = rng() % 10; } while (g[fr][fc] == '*' || (fr == cr && fc == cc));
}

/* ★ 爬山搜出来的两张图（搜法见页面第 ④ 步；这里只把结果存下来复验）。
   ⚠ 它们是「搜到的」，不是「最大的」—— 头一轮爬山（12 次重启）搜到答案 506，
   把重启次数加到 40 就变成了 635。**搜得更久还能更大，所以这个数只是下界。** */
static const char* WORST_ANS[10] = {
    "**.***.***", "*...**.*.*", ".*.*.*....", "**.*.....*", "*.*.....*.",
    "*.....*..*", "...**.****", "....*.*.**", "**.*......", ".*.**.*...",
};
static const char* WORST_LOOP[10] = {
    ".*.***....", "*.....*.*.", "........*.", ".*....*.*.", "....***.*.",
    ".....*..*.", "*...**....", "*...***.**", ".**.**..*.", "*.*.*.*.**",
};

/** 一张固定地图上，枚举所有 (牛, 农夫) 起点，返回最大答案和最大步数。 */
static pair<long long, long long> scanAll() {
    long long ba = 0, bs = 0;
    for (int a = 0; a < 100; a++) {
        if (g[a / 10][a % 10] == '*') continue;
        for (int b = 0; b < 100; b++) {
            if (b == a || g[b / 10][b % 10] == '*') continue;
            long long st;
            long long r = solve(a / 10, a % 10, b / 10, b % 10, OK, 0, st);
            ba = max(ba, r); bs = max(bs, st);
        }
    }
    return {ba, bs};
}

static const char* SAMPLE[10] = {
    "*...*.....", "......*...", "...*...*..", "..........", "...*.F....",
    "*.....*...", "...*......", "..C......*", "...*.*....", ".*.*......",
};

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

    /* ① 官方样例 */
    {
        int cr = 0, cc = 0, fr = 0, fc = 0;
        for (int i = 0; i < 10; i++) {
            memcpy(g[i], SAMPLE[i], 11);
            for (int j = 0; j < 10; j++) {
                if (g[i][j] == 'C') { cr = i; cc = j; }
                if (g[i][j] == 'F') { fr = i; fc = j; }
            }
        }
        long long st;
        long long a = solve(cr, cc, fr, fc, OK, 0, st);
        long long b = solve(cr, cc, fr, fc, GUESS, 100000, st);
        long long c = solve(cr, cc, fr, fc, GUESS, 300, st);
        long long d = solve(cr, cc, fr, fc, TURN, 100000, st);
        long long e = solve(cr, cc, fr, fc, CROSS, 100000, st);
        if (!CSV) printf("① 官方样例：正解 %lld｜十万上限 %lld｜上限 300 %lld｜转向不占时间 %lld｜顺序移动 %lld\n",
                         a, b, c, d, e);
        row("sample", {a, b, c, d, e});
    }

    /* ② 随机地图上的分布 */
    const int R = 20000;
    {
        if (!CSV) printf("\n② 随机地图 %d 组（按障碍密度分档）\n", R);
        vector<long long> out;
        for (int pct : {5, 10, 20, 30, 40}) {
            int zero = 0;
            long long mxA = 0, mxS = 0;
            vector<long long> ans;
            for (int s = 1; s <= R; s++) {
                int cr, cc, fr, fc, st2;
                (void)st2;
                gen(s, pct, cr, cc, fr, fc);
                long long st;
                long long a = solve(cr, cc, fr, fc, OK, 0, st);
                if (a == 0) zero++; else ans.push_back(a);
                mxA = max(mxA, a); mxS = max(mxS, st);
            }
            sort(ans.begin(), ans.end());
            long long med = ans.empty() ? 0 : ans[ans.size() / 2];
            out.push_back(zero); out.push_back(med); out.push_back(mxA); out.push_back(mxS);
            if (!CSV) printf("  密度 %2d%%：永远抓不到 %d 组（%.1f%%）｜抓得到的中位数 %lld 步、最大 %lld"
                             "｜判定「抓不到」最多走 %lld 步\n",
                             pct, zero, zero * 100.0 / R, med, mxA, mxS);
        }
        row("dist", out);
    }

    /* ③ ★★★ 专门去找：爬山搜出来的两张图 */
    {
        for (int i = 0; i < 10; i++) memcpy(g[i], WORST_ANS[i], 11);
        auto p = scanAll();
        for (int i = 0; i < 10; i++) memcpy(g[i], WORST_LOOP[i], 11);
        auto q = scanAll();
        if (!CSV) printf("\n③ 爬山搜出来的两张图：最大答案 %lld（那张图上判环也要 %lld 步）"
                         "｜最长判环 %lld 步（那张图上最大答案 %lld）\n", p.first, p.second, q.second, q.first);
        row("worst", {p.first, p.second, q.first, q.second});
    }

    /* ④ 上限拍多少才够 */
    {
        if (!CSV) printf("\n④ 把上限从 100000 换成别的：%d 组随机地图里错多少组\n", R);
        vector<long long> out;
        for (long long lim : {100, 200, 300, 500, 1000, 2000}) {
            int bad = 0;
            for (int s = 1; s <= R; s++) {
                int cr, cc, fr, fc;
                gen(s, 0, cr, cc, fr, fc);
                long long st;
                long long ref = solve(cr, cc, fr, fc, OK, 0, st);
                long long got = solve(cr, cc, fr, fc, GUESS, lim, st);
                if (ref != got) bad++;
            }
            out.push_back(bad);
            if (!CSV) printf("  上限 %5lld：错 %d 组\n", lim, bad);
        }
        row("limit", out);
    }

    /* ⑤ 三个错法的抓获率 —— ⚠ 「两版一起输出 0」的轮要单独数出来 */
    {
        if (!CSV) printf("\n⑤ 三个错法各被抓多少（每档 300 轮）\n");
        vector<long long> out;
        const char* nm[3] = {"上限拍成 300", "转向不占时间", "顺序移动"};
        const Kind KS[3] = {GUESS, TURN, CROSS};
        const long long LS[3] = {300, 100000, 100000};
        for (int k = 0; k < 3; k++) {
            int bad = 0, bothZero = 0;
            for (int s = 1; s <= 300; s++) {
                int cr, cc, fr, fc;
                gen(s, 0, cr, cc, fr, fc);
                long long st;
                long long ref = solve(cr, cc, fr, fc, OK, 0, st);
                long long got = solve(cr, cc, fr, fc, KS[k], LS[k], st);
                if (ref == 0 && got == 0) bothZero++;
                if (ref != got) bad++;
            }
            out.push_back(bad); out.push_back(bothZero);
            if (!CSV) printf("  %s：抓到 %d / 300（其中 %d 轮两版一起输出 0，那些轮验的是零）\n",
                             nm[k], bad, bothZero);
        }
        row("catch", out);
    }

    /* ⑥ 判重版实际走了多少步 */
    {
        long long tot = 0, mx = 0;
        for (int s = 1; s <= R; s++) {
            int cr, cc, fr, fc;
            gen(s, 0, cr, cc, fr, fc);
            long long st;
            solve(cr, cc, fr, fc, OK, 0, st);
            tot += st; mx = max(mx, st);
        }
        if (!CSV) printf("\n⑥ 判重版实际走的分钟数：%d 组平均 %.2f 步、最大 %lld 步"
                         "（而「循环十万次」那版在抓不到时**每次都走满十万步**）\n",
                         R, tot * 1.0 / R, mx);
        row("steps", {tot * 100 / R, mx});
    }
    return 0;
}

// P1518 对拍生成器：`./p1518Gen <seed> [密度]`
//   密度 = 障碍格的百分比（默认 seed 决定，5 ~ 40）
//
// 造法：10 × 10 的格子按密度随机撒 `*`，再在空地里随机放 `C` 和 `F`（不同格）。
// ⇒ 造出来的一定是合法输入（题面保证只有一个 C、一个 F，且不在同一格）。
//
// ★ 这道题的生成器没有「造得对不对」的问题 —— 任何 10 × 10 的图都是合法输入。
//   ⚠ 但它有另一个问题，而且是这一页的主线之一：
//   **随机地图上，70% ~ 85% 的图是「永远抓不到」的**（页面第 ③ 步），
//   而那些图上正解和一堆错法都输出 0，**对拍在那些轮里验的是零**。
//   ⇒ [第 14 章 P1746](/sol/p1746/) 那条「『一致』有两种」在这道题上是**常态**，不是例外。

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

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    mt19937 rng(seed * 2654435761u + 11u);
    int pct = argc > 2 ? atoi(argv[2]) : (int)(rng() % 36 + 5);
    pct = max(0, min(90, pct));

    char g[10][11];
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) g[i][j] = ((int)(rng() % 100) < pct) ? '*' : '.';
        g[i][10] = 0;
    }
    int cr, cc, fr, fc;
    do { cr = rng() % 10; cc = rng() % 10; } while (g[cr][cc] == '*');
    do { fr = rng() % 10; fc = rng() % 10; } while (g[fr][fc] == '*' || (fr == cr && fc == cc));
    g[cr][cc] = 'C';
    g[fr][fc] = 'F';

    for (int i = 0; i < 10; i++) printf("%s\n", g[i]);
    return 0;
}