洛谷 P1451 求细胞数量

// P1451 求细胞数量 —— 能 AC 的那一版
//
// 和上一道 [P1596](/sol/p1596/) 是**同一份代码**，只差**两个旋钮**：
//
//              连通性        什么算「格子」
//   P1596      ★ 八连通       字符 == 'W'
//   P1451      ★ 四连通       字符 != '0'    ← 注意是字符 '0'，不是数字 0
//
// 题面原话：「沿细胞数字**上下左右**若还是细胞数字则为同一细胞」——
//   · **上下左右** ⇒ 四连通，没有斜角；
//   · **还是细胞数字** ⇒ 只要非 0 就行，**不要求是同一个数字**
//     （样例里 `234` 和 `1` 是连着的一坨，算一个细胞）。
//
// ⚠ 「和上一道几乎一样」是危险信号，不是安全信号：
//   这一页三个错法里有两个，就是把上面那两个旋钮各拧错了一个。

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

static int n, m;
static char g[105][105];
static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

static void dfs(int x, int y) {
    g[x][y] = '0';                          // 走过就抹成 0
    for (int d = 0; d < 4; d++) {
        int nx = x + DX[d], ny = y + DY[d];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (g[nx][ny] != '0') dfs(nx, ny);  // ★ 只要非 '0'，不管是不是同一个数字
    }
}

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

    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] != '0') { cnt++; dfs(i, j); }

    printf("%d\n", cnt);
    return 0;
}

// P1451 ⚠ 错法一：`!= '0'` 少写了两个引号，写成 `!= 0`
//
// `g[i][j]` 是 **char**。字符 `'0'` 的 ASCII 是 **48**，而 `0` 是数字零。
// ⇒ `g[i][j] != 0` 对**每一个字符**都成立（输入里根本没有 `\0`）。
//
// ★★★ 而它给出的**不是错误答案，是段错误**（本机实测退出码 139）——
//   因为这份代码没有独立的 `vis` 数组，它靠「把走过的格子抹成 `'0'`」来兼职标记。
//   可 `'0' != 0` 仍然成立 ⇒ **抹了等于没抹** ⇒ 两个相邻格子来回递归，8 MB 栈几毫秒就没了。
//
// ⇒ ★★★ 同一个笔误，同时破坏了**两件事**：「什么算格子」和「怎么标记走过」。
//   而它们本来是两件事 —— 是「省掉一个 vis 数组」这个常见写法把它们绑在了一起。
//   ⇒ 对照 p1451ZeroVis.cpp：**同一个笔误、独立 vis，它只是安静地输出 1**（WA，不崩）。
//   **「省一个数组」把一个 WA 升级成了 RE。**

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

static int n, m;
static char g[105][105];
static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

static void dfs(int x, int y) {
    g[x][y] = '0';
    for (int d = 0; d < 4; d++) {
        int nx = x + DX[d], ny = y + DY[d];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (g[nx][ny] != 0) dfs(nx, ny);    // ⚠ 就是这里：'0' 写成了 0
    }
}

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 0; i < n; i++) if (scanf("%s", g[i]) != 1) return 0;
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] != 0) { cnt++; dfs(i, j); }
    printf("%d\n", cnt);
    return 0;
}

// P1451 ⚠ 错法一的**孪生版**：同一个笔误（`!= '0'` 写成 `!= 0`），但用独立的 vis 数组
//
// 和 p1451Zero.cpp 的差别只有一处：走过的格子记在 `vis[][]` 里，不去抹 `g[][]`。
//
// ⇒ 同一个笔误，结果完全不同：
//   · p1451Zero（抹成 '0' 当标记）：`'0' != 0` 仍成立 ⇒ 抹了等于没抹 ⇒ **段错误**；
//   · 这一版（独立 vis）          ：标记照常生效 ⇒ 整张网格是一个细胞 ⇒ **安静地输出 1**。
//
// ★★★ 一句话：**「省掉一个 vis 数组」这个常见写法，把一个 WA 升级成了 RE。**
//   ⚠ 而 RE 在对拍里还有第二重代价：崩一次要付出进程退出的开销
//     （第 5 章 P1042 那条：让崩溃版进对拍表会把对拍拖垮）。

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

static int n, m;
static char g[105][105];
static bool vis[105][105];
static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

static void dfs(int x, int y) {
    vis[x][y] = true;                       // ★ 标记记在别处，不动 g
    for (int d = 0; d < 4; d++) {
        int nx = x + DX[d], ny = y + DY[d];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (!vis[nx][ny] && g[nx][ny] != 0) dfs(nx, ny);   // ⚠ 同一个笔误
    }
}

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 0; i < n; i++) if (scanf("%s", g[i]) != 1) return 0;
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (!vis[i][j] && g[i][j] != 0) { cnt++; dfs(i, j); }
    printf("%d\n", cnt);
    return 0;
}

// P1451 ⚠ 错法二：以为「同一个数字」才算同一细胞
//
// 题面写的是「沿细胞数字上下左右**若还是细胞数字**则为同一细胞」——
// 「还是细胞数字」= 只要非 0，**不要求相等**。
//
// 而「1 到 9 代表细胞」这句话很容易被读成「不同的数字是不同的细胞」。
// ⇒ 这一版把条件写成 `g[nx][ny] == g[x][y]`，于是同一坨里数字一变就断开。
//
// ★ 它和错法一、错法三合起来说明一件事：**这道题三个 bug，全都在「读题」上，
//   一个都不在算法上** —— 三份代码的 DFS 骨架一模一样。

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

static int n, m;
static char g[105][105];
static const int DX[4] = {-1, 1, 0, 0};
static const int DY[4] = {0, 0, -1, 1};

static void dfs(int x, int y, char c) {
    g[x][y] = '0';
    for (int d = 0; d < 4; d++) {
        int nx = x + DX[d], ny = y + DY[d];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (g[nx][ny] == c) dfs(nx, ny, c);  // ⚠ 就是这里：要求数字相等
    }
}

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 0; i < n; i++) if (scanf("%s", g[i]) != 1) return 0;
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] != '0') { cnt++; dfs(i, j, g[i][j]); }
    printf("%d\n", cnt);
    return 0;
}

// P1451 ⚠ 错法三：把上一道题的**八连通**顺手搬了过来
//
// [P1596](/sol/p1596/) 是八连通、这道题是四连通 —— 两份代码除了这一处几乎一样，
// 而「刚写完那道题」恰恰是最容易搬错的时候。
//
// ★ 注意它和 P1596 那个错法是**同一个旋钮拧向相反的方向**：
//   那边是「该八连通写成了四连通」，这边是「该四连通写成了八连通」。
//   ⇒ 抓获率的曲面形状也跟着反过来（见解析页第 ④ 步那张表）。

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

static int n, m;
static char g[105][105];
static const int DX[8] = {-1, -1, -1, 0, 0, 1, 1, 1};   // ⚠ 就是这两行
static const int DY[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

static void dfs(int x, int y) {
    g[x][y] = '0';
    for (int d = 0; d < 8; d++) {
        int nx = x + DX[d], ny = y + DY[d];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (g[nx][ny] != '0') dfs(nx, ny);
    }
}

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 0; i < n; i++) if (scanf("%s", g[i]) != 1) return 0;
    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] != '0') { cnt++; dfs(i, j); }
    printf("%d\n", cnt);
    return 0;
}

// 数据生成器（P1451 对拍用）：`./p1451Gen <seed> [density] [n] [m]`
//
//   density = 每个格子是**细胞**（非 0）的概率百分数，默认 30。
//
// ⚠ 两条和 P1596 不一样的：
//   ① 非零格子还要**随机挑 1..9 里的一个数字** ——
//      而「数字挑得散不散」直接决定 `p1451Same`（以为同数字才连通）抓不抓得到：
//      全用同一个数字 ⇒ 那个 bug **精确的 0**；
//   ② 这道题是**四连通**，所以「只斜着挨着的一对」在这里是**反过来**起作用的
//      （见解析页第 ④ 步）。
//
//   level 由第五个参数给：0 = 数字随机（默认），1 = ★ **所有非零格都用同一个数字**。

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

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

    printf("%d %d\n", n, m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (ri(1, 100) > density) putchar('0');
            else putchar(level == 1 ? '7' : (char)('0' + ri(1, 9)));
        }
        putchar('\n');
    }
    return 0;
}