洛谷 P1162 填涂颜色

// P1162 填涂颜色 —— 能 AC 的那一版
//
// ★ 关键的一步是**换个问法**：
//   题目问「哪些 0 在圈**里**」，直接找「里面」很难 —— 你根本不知道从哪个 0 出发。
//   反过来问就简单了：**哪些 0 在圈外？**
//   题面自己把定义给全了：「从某个 0 出发，只向上下左右移动且仅经过其他 0，
//   **无法到达方阵的边界**，就认为这个 0 在闭合圈内」。
//
//   ⇒ 从**所有边界上的 0** 出发做一次 flood fill，标记「外面的 0」；
//     剩下没被标记的 0，就是圈里的 ⇒ 填 2。
//
// ⚠ 起点必须是**四条边上的每一个 0**，不是随便挑一个格子 ——
//   闭合圈可能贴着某条边，那条边上一个 0 都没有（见 p1162Corner.cpp 那个错法）。

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

static int n;
static int a[35][35];
static bool out_[35][35];
static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

static void flood(int sx, int sy) {
    vector<pair<int, int>> q{{sx, sy}};
    out_[sx][sy] = true;
    for (size_t h = 0; h < q.size(); h++) {
        int x = q[h].first, y = q[h].second;
        for (int d = 0; d < 4; d++) {
            int nx = x + DX[d], ny = y + DY[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (a[nx][ny] != 0 || out_[nx][ny]) continue;
            out_[nx][ny] = true;
            q.push_back({nx, ny});
        }
    }
}

int main() {
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (scanf("%d", &a[i][j]) != 1) return 0;

    for (int i = 0; i < n; i++) {                    // ★ 四条边上的每一个 0 都当起点
        if (a[i][0] == 0 && !out_[i][0]) flood(i, 0);
        if (a[i][n - 1] == 0 && !out_[i][n - 1]) flood(i, n - 1);
    }
    for (int j = 0; j < n; j++) {
        if (a[0][j] == 0 && !out_[0][j]) flood(0, j);
        if (a[n - 1][j] == 0 && !out_[n - 1][j]) flood(n - 1, j);
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            printf("%d%c", (a[i][j] == 0 && !out_[i][j]) ? 2 : a[i][j], j + 1 == n ? '\n' : ' ');
    return 0;
}

// P1162 ⚠ 错法一：直接找「里面」——从第一个**不在边界上**的 0 出发填 2
//
// 这是不换问法时最自然的想法：「圈里的 0 总不在边界上吧，那就找一个非边界的 0 开始填」。
//
// ⚠ 而**圈外也有大把非边界的 0**。样例第一行下面那个 `(1,0)`、`(1,1)` 都是圈外的 0，
//   却都不在边界上（其实 (1,0) 在边界列上，但 (1,1) 不在）。
//   ⇒ 它从圈外开始填，把外面一大片染成 2。
//
// ★ 这道题的题目描述里那句「想想为什么不能从里面开始」，说的就是它。
//   ⇒ **「里面」这个概念，只有相对「外面」才定义得出来** ——
//     题面自己的定义也是这么写的（「无法到达方阵的边界」）。

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

static int n;
static int a[35][35];
static bool mark[35][35];
static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

static void flood(int sx, int sy) {
    vector<pair<int, int>> q{{sx, sy}};
    mark[sx][sy] = true;
    for (size_t h = 0; h < q.size(); h++) {
        int x = q[h].first, y = q[h].second;
        for (int d = 0; d < 4; d++) {
            int nx = x + DX[d], ny = y + DY[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (a[nx][ny] != 0 || mark[nx][ny]) continue;
            mark[nx][ny] = true;
            q.push_back({nx, ny});
        }
    }
}

int main() {
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (scanf("%d", &a[i][j]) != 1) return 0;

    bool done = false;                               // ⚠ 找第一个「非边界的 0」就开填
    for (int i = 1; i < n - 1 && !done; i++)
        for (int j = 1; j < n - 1 && !done; j++)
            if (a[i][j] == 0) { flood(i, j); done = true; }

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

// P1162 ⚠ 错法二：只从左上角 (0,0) 出发做一次 flood fill
//
// 「外面的 0 是连通的，从随便哪个外面的 0 出发都一样」—— 这句话**大体上对**，
// 而 (0,0) 看起来是最省事的起点。
//
// ⚠⚠ 我第一版在这儿写的触发条件是「`a[0][0] != 0`」（闭合圈贴着左上角）——
//   **实测 300 轮里它一次都没出现，而这一版被抓了 197 次。推的，错了。**
//
// ★★★ 真正的原因是那句「大体上对」的话本身就是错的：**外面的 0 不一定连通。**
//   1 可以把边界上的 0 切成好几个互不相通的小口袋（比如右上角那一个孤零零的 0）——
//   它们**都在外面**（本来就贴着边界），可**从 (0,0) 走不过去**
//   ⇒ 这一版把它们当成「圈里」，全填成 2。
//
// ⇒ 真触发条件：**`a[0][0] != 0`，或者「能从边界出发到达的 0」被切成了两块以上**。
//   实测这个计数和抓获数**一格不差**：合法数据 197 / 197，随机方阵 299 / 299
//   （[第 11 章 P1115](/sol/p1115/) 那条：抓获数不是概率，是一个数得出来的计数）。
//
// ⇒ 而正解从**四条边上的每一个 0** 出发，恰好不在乎外面分成几块。

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

static int n;
static int a[35][35];
static bool out_[35][35];
static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

static void flood(int sx, int sy) {
    vector<pair<int, int>> q{{sx, sy}};
    out_[sx][sy] = true;
    for (size_t h = 0; h < q.size(); h++) {
        int x = q[h].first, y = q[h].second;
        for (int d = 0; d < 4; d++) {
            int nx = x + DX[d], ny = y + DY[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (a[nx][ny] != 0 || out_[nx][ny]) continue;
            out_[nx][ny] = true;
            q.push_back({nx, ny});
        }
    }
}

int main() {
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (scanf("%d", &a[i][j]) != 1) return 0;

    if (a[0][0] == 0) flood(0, 0);                   // ⚠ 就是这里：只有一个起点

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            printf("%d%c", (a[i][j] == 0 && !out_[i][j]) ? 2 : a[i][j], j + 1 == n ? '\n' : ' ');
    return 0;
}

// ★★★ 「随便扔一把 0 和 1」，有多大概率是这道题的**合法输入**？
//
// 用法：./p1162Rand [rounds]        人话版（默认每格 2000 轮）
//       ./p1162Rand [rounds] csv    给 check:viz 用
//
// 题面的保证有三条：① 只有一个闭合圈；② 圈内至少有一个 0；③ 圈内的 0 连通。
// 合起来就是一句可判定的话：**「被 1 围住、到不了边界的那些 0」非空，而且四连通。**
//
// 这份程序扫 n × 密度，看随机 01 方阵里有多大比例满足它。
//
// ⇒ 这一页真正想说的是：**有一类题，最难写的不是正解，是生成器。**
//   如果你懒得构造、直接把随机方阵喂进对拍 —— 绝大多数轮次里，
//   **你验的是一道题面根本不存在的题**；而所有版本在那些数据上很可能一起「错」，
//   于是对拍还全绿。

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

static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

/** 题面那三条保证：返回 true 表示这张方阵是合法输入 */
static bool legal(const vector<vector<int>>& a, int n) {
    vector<vector<char>> out_(n, vector<char>(n, 0));
    vector<pair<int, int>> q;
    auto push = [&](int x, int y) {
        if (a[x][y] == 0 && !out_[x][y]) { out_[x][y] = 1; q.push_back({x, y}); }
    };
    for (int i = 0; i < n; i++) { push(i, 0); push(i, n - 1); }
    for (int j = 0; j < n; j++) { push(0, j); push(n - 1, j); }
    for (size_t h = 0; h < q.size(); h++)
        for (int d = 0; d < 4; d++) {
            int nx = q[h].first + DX[d], ny = q[h].second + DY[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            push(nx, ny);
        }

    vector<pair<int, int>> inside;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (a[i][j] == 0 && !out_[i][j]) inside.push_back({i, j});
    if (inside.empty()) return false;                       // ② 圈内至少有一个 0

    vector<vector<char>> vis(n, vector<char>(n, 0));        // ③ 圈内的 0 要连通
    vector<pair<int, int>> s{inside[0]};
    vis[inside[0].first][inside[0].second] = 1;
    size_t seen = 1;
    for (size_t h = 0; h < s.size(); h++)
        for (int d = 0; d < 4; d++) {
            int nx = s[h].first + DX[d], ny = s[h].second + DY[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (a[nx][ny] != 0 || out_[nx][ny] || vis[nx][ny]) continue;
            vis[nx][ny] = 1; s.push_back({nx, ny}); seen++;
        }
    return seen == inside.size();
}

static const int NS[4] = {5, 10, 20, 30};
static const int DS[7] = {10, 20, 30, 40, 50, 60, 70};

int main(int argc, char** argv) {
    int rounds = (argc > 1) ? atoi(argv[1]) : 2000;
    bool csv = (argc > 2 && string(argv[2]) == "csv");

    int tab[4][7];
    long long total = 0, ok = 0;
    for (int p = 0; p < 4; p++)
        for (int b = 0; b < 7; b++) {
            int n = NS[p], d = DS[b], good = 0;
            mt19937 rng(20260827u + (unsigned)(p * 1000 + d));
            for (int r = 0; r < rounds; r++) {
                vector<vector<int>> a(n, vector<int>(n, 0));
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < n; j++)
                        a[i][j] = ((int)(rng() % 100u) < d) ? 1 : 0;
                if (legal(a, n)) good++;
            }
            tab[p][b] = good; total += rounds; ok += good;
        }

    int bestP = 0, bestB = 0;
    for (int p = 0; p < 4; p++)
        for (int b = 0; b < 7; b++)
            if (tab[p][b] > tab[bestP][bestB]) { bestP = p; bestB = b; }

    if (csv) {
        printf("rounds,%d\ntotal,%lld\nok,%lld\n", rounds, total, ok);
        printf("bestN,%d\nbestD,%d\nbest,%d\n", NS[bestP], DS[bestB], tab[bestP][bestB]);
        for (int p = 0; p < 4; p++) {
            printf("n%d", NS[p]);
            for (int b = 0; b < 7; b++) printf(",%d", tab[p][b]);
            printf("\n");
        }
        return 0;
    }

    printf("随机 01 方阵，每格 %d 轮，有几轮是这道题的**合法输入**：\n\n", rounds);
    printf("        ");
    for (int b = 0; b < 7; b++) printf("%8d%%", DS[b]);
    printf("\n");
    for (int p = 0; p < 4; p++) {
        printf("  n=%2d  ", NS[p]);
        for (int b = 0; b < 7; b++) printf("%9d", tab[p][b]);
        printf("\n");
    }
    printf("\n  一共 %lld 轮，合法的 %lld 轮 —— **%.2f%%**。\n", total, ok, 100.0 * (double)ok / (double)total);
    printf("  最好的一格是 n = %d、密度 %d%%（%d / %d）。\n", NS[bestP], DS[bestB], tab[bestP][bestB], rounds);
    printf("\n  ⇒ **有一类题，最难写的不是正解，是生成器。**\n");
    printf("    把随机方阵直接喂进对拍，绝大多数轮次里你验的是**一道不存在的题** ——\n");
    printf("    而那些数据上各个版本很可能一起「错」，于是对拍还全绿。\n");
    return 0;
}

// 数据生成器（P1162 对拍用）：`./p1162Gen <seed> [n] [level]`
//
//   level 0（默认）★ **构造一个合法的闭合圈**（下面那四步）
//   level 1        ⚠ **纯随机 01 方阵**（密度 50%）—— 故意造非法数据，
//                  用来演示「把随机方阵喂进对拍」会发生什么（见解析页第 ⑤ 步）
//
// ★★★ 这道题最难写的不是正解，是**生成器** —— 而这正是这一页要说的事。
//
// 题面的保证有三条，缺一条数据就是非法的：
//   ① 方阵内**只有一个**闭合圈；② 圈内**至少有一个 0**；③ 圈内的 0 是**连通的**。
// 随便扔一把 0 和 1，满足这三条的比例低到什么程度？见 p1162Rand.cpp。
//
// ⇒ 所以只能**构造**，不能随机：
//   ① 先在**不碰边界**的范围里长一团连通的格子 R（这就是「圈内」）；
//   ② 把「和 R 四连通相邻、但不属于 R」的那一圈全设成 1（这就是「闭合圈」）；
//   ③ 其余全 0。
//   ④ ★ **造完还要用题面的定义验一遍**（从边界 flood 一次，看圈内是不是恰好等于 R），
//      不满足就重造 —— **构造出来的东西也得验，不能想当然**。

#include <bits/stdc++.h>
using namespace std;
static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

int main(int argc, char** argv) {
    rng.seed((argc > 1) ? (unsigned)atoi(argv[1]) : 1);
    int n = (argc > 2) ? atoi(argv[2]) : ri(4, 12);
    int level = (argc > 3) ? atoi(argv[3]) : 0;
    if (n < 3) n = 3;

    if (level == 1) {                                // ⚠ 纯随机：绝大多数不是合法输入
        printf("%d\n", n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                printf("%d%c", ri(0, 1), j + 1 == n ? '\n' : ' ');
        return 0;
    }

    vector<vector<int>> a;
    for (int attempt = 0; ; attempt++) {
        /* ① 在 [1, n-2] 的范围里长一团四连通的 R */
        set<pair<int, int>> R;
        int sx = ri(1, n - 2), sy = ri(1, n - 2);
        R.insert({sx, sy});
        int want = ri(1, max(1, (n - 2) * (n - 2) / 2));
        for (int t = 0; (int)R.size() < want && t < 500; t++) {
            auto it = R.begin();
            advance(it, (int)(rng() % (unsigned)R.size()));
            int d = ri(0, 3);
            int nx = it->first + DX[d], ny = it->second + DY[d];
            if (nx < 1 || nx > n - 2 || ny < 1 || ny > n - 2) continue;
            R.insert({nx, ny});
        }

        /* ② R 的四连通外一层设成 1，其余 0 */
        a.assign(n, vector<int>(n, 0));
        for (auto& p : R)
            for (int d = 0; d < 4; d++) {
                int nx = p.first + DX[d], ny = p.second + DY[d];
                if (R.count({nx, ny})) continue;
                a[nx][ny] = 1;
            }

        /* ④ 拿题面的定义验一遍：从边界 flood，圈内应当恰好等于 R */
        vector<vector<char>> out_(n, vector<char>(n, 0));
        vector<pair<int, int>> q;
        auto push = [&](int x, int y) {
            if (a[x][y] == 0 && !out_[x][y]) { out_[x][y] = 1; q.push_back({x, y}); }
        };
        for (int i = 0; i < n; i++) { push(i, 0); push(i, n - 1); }
        for (int j = 0; j < n; j++) { push(0, j); push(n - 1, j); }
        for (size_t h = 0; h < q.size(); h++)
            for (int d = 0; d < 4; d++) {
                int nx = q[h].first + DX[d], ny = q[h].second + DY[d];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                push(nx, ny);
            }
        set<pair<int, int>> inside;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (a[i][j] == 0 && !out_[i][j]) inside.insert({i, j});
        if (!inside.empty() && inside == R) break;
        if (attempt > 200) { n++; }                  // 实在造不出来就把方阵放大一点
    }

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