P1596 [USACO10OCT] Lake Counting S · 习题解析

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1596，日期见页头。两边不一致时信原站。

题目描述

由于最近的降雨，水在农夫约翰的田地里积聚了。田地可以表示为一个 N × M 的矩形（1 ≤ N ≤ 100；1 ≤ M ≤ 100）。每个方格中要么是水（W），要么是干地（.）。农夫约翰想要弄清楚他的田地里形成了多少个水塘。一个水塘是由连通的水方格组成的，其中一个方格被认为与它的八个邻居相邻。给定农夫约翰田地的示意图，确定他有多少个水塘。

输入格式

第 1 行：两个用空格分隔的整数：N 和 M。

第 2 行到第 N+1 行：每行 M 个字符，表示农夫约翰田地的一行。

每个字符要么是 W，要么是 .。字符之间没有空格。

输出格式

第 1 行：农夫约翰田地中的水塘数量。

说明 / 提示

输出详情：共有三个水塘：一个在左上角，一个在左下角，还有一个沿着右侧。

（洛谷题面注：由 ChatGPT 4o 翻译）

输入输出样例

输入

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出

1和本章正文只差一个常量

p1596.cpp★ 这一版就能 AC

// P1596 [USACO10OCT] Lake Counting S —— 能 AC 的那一版
//
// 数连通块，和本章正文那份 fast.cpp 是同一件事，只差**一个常量**：
//
//     本章正文：四连通（上下左右）      dx[4] / dy[4]
//     这道题  ：★ **八连通**（还带四个斜角） dx[8] / dy[8]
//
// 题面原话：「一个方格被认为与它的**八个**邻居相邻」。
//
// ⚠ 而「只差一个常量」正是这道题最危险的地方 ——
//   照搬模板忘了改方向数组，本地怎么看都对（见解析页第 ③ 步那条曲线）。
//
// 规模：n, m <= 100 ⇒ 最多 10⁴ 个格子，递归最深 10⁴ 层，离爆栈还远（第 30 章量过 28 万层）。

#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] = '.';                          // 走过就填平，等于 vis 数组
    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] == 'W') 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] == 'W') { cnt++; dfs(i, j); }

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

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

数连通块，第 13 章正文从头讲到尾了。这道题只把方向数组从 4 个改成 8 个：

本章正文：四连通            dx[4] = {-1, 1, 0, 0}
这道题  ：★ 八连通（带斜角）  dx[8] = {-1,-1,-1, 0, 0, 1, 1, 1}

规模：N, M ≤ 100 ⇒ 最多 10⁴ 个格子，递归最深 10⁴ 层，离爆栈还远（第 30 章实测本机 8 MB 栈大约 28 万层）。

★ 而「只差一个常量」正是这道题最危险的地方

这一页整页只做一件事：把「照搬模板忘了改方向数组」这个 bug 的抓获率量出来。

结论提前说：它不是一个数，是一张曲面 —— 而且这张曲面上，「顺手写的对拍生成器」最常待的那个角落，抓获率低得吓人。

2⚠ 那个错法：照搬四连通

p1596Four.cpp⚠ 四连通（照搬模板）

// P1596 ⚠ 错法：照搬本章模板的**四连通**
//
// 和 p1596.cpp 只差方向数组那两行 —— 而题面第三句就写着「与它的**八个**邻居相邻」。
//
// ★ 这一页真正想量的是它：**这个 bug 的抓获率，是一条两头都掉到 0 的单峰曲线。**
//   · 水很稀（每个 W 都孤立）⇒ 四连通和八连通都等于 W 的个数，**完全一样**；
//   · 水很密（连成一大片）  ⇒ 两边都是 1，**还是一样**；
//   · 只有**中间那段密度**，斜角才既存在、又起作用。
//   ⇒ 顺手写的生成器落在哪个密度上，直接决定你抓不抓得到。见 p1596Count.cpp 那条曲线。

#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] = '.';
    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] == 'W') 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] == 'W') { cnt++; dfs(i, j); }
    printf("%d\n", cnt);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

官方样例它就挂了：题面答案 3，它给 13。

★ 而这不是运气 —— 官方样例的密度挑在了刀口上

样例是 10 × 12 = 120 格，其中 W 有 31 个 ⇒ 密度 25.8%。下一步那张表会看到：抓获率的峰正好在 30% 附近。

⇒ 出题人给的样例，密度恰好落在这个 bug 最容易现形的地方。（第 8 章 P2249 那条「样例有时候比对拍还狠」的又一次 —— 而这次能说出为什么。）

3★★★ 抓获率是一张曲面，不是一个数

p1596Count.cpp扫两个旋钮：n × 密度

// ★★★ 抓获率不是一个数，是一张**曲面** —— 而它有两个旋钮，不是一个
//
// 用法：./p1596Count [rounds]        人话版（默认每格 200 轮）
//       ./p1596Count [rounds] csv    给 check:viz 用
//
// 「四连通写成八连通」这个 bug 抓不抓得到，取决于**两个**旋钮：网格边长 n 和水的密度。
//
// ⚠ 我一开始只扫了密度（固定 30×30），得到的结论是错的 ——
//   那张表上「低密度」那一头是 **192 / 200**，一点都没掉下去。
//   ⇒ 真正管事的不是密度本身，是 **W 的个数 ≈ n² × 密度**，以及
//     「有没有一对 W 只斜着挨着」。密度低但格子多，照样有的是斜角。
//
// ⇒ 所以这里扫的是**两个旋钮**：n ∈ {3, 5, 8, 15, 30} × 密度 ∈ {5,15,30,50,70,85,95}。
//   精确的 0 落在**左上角那一块**（小网格 ＋ 低密度）——
//   而那正是「顺手写的对拍生成器」最常待的地方。

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

static int n;
static vector<string> g;
static vector<vector<char>> vis;
static const int DX8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
static const int DY8[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

static int components(int dirs) {
    vis.assign(n, vector<char>(n, 0));
    int cnt = 0;
    vector<pair<int, int>> q;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (g[i][j] != 'W' || vis[i][j]) continue;
            cnt++;
            q.clear(); q.push_back({i, j}); vis[i][j] = 1;
            for (size_t h = 0; h < q.size(); h++) {
                int x = q[h].first, y = q[h].second;
                for (int d = 0; d < 8; d++) {
                    if (dirs == 4 && DX8[d] != 0 && DY8[d] != 0) continue;   // 四连通就跳过斜角
                    int nx = x + DX8[d], ny = y + DY8[d];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                    if (g[nx][ny] != 'W' || vis[nx][ny]) continue;
                    vis[nx][ny] = 1; q.push_back({nx, ny});
                }
            }
        }
    return cnt;
}

static const int NS[5] = {3, 5, 8, 15, 30};
static const int DS[7] = {5, 15, 30, 50, 70, 85, 95};

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

    int tab[5][7];
    for (int a = 0; a < 5; a++)
        for (int b = 0; b < 7; b++) {
            n = NS[a];
            int d = DS[b];
            mt19937 rng(20260827u + (unsigned)(a * 100 + d));
            int bad = 0;
            for (int r = 0; r < rounds; r++) {
                g.assign(n, string(n, '.'));
                for (int i = 0; i < n; i++)
                    for (int j = 0; j < n; j++)
                        if ((int)(rng() % 100u) < d) g[i][j] = 'W';
                if (components(4) != components(8)) bad++;
            }
            tab[a][b] = bad;
        }

    int zeros = 0, best = 0, bestA = 0, bestB = 0;
    for (int a = 0; a < 5; a++)
        for (int b = 0; b < 7; b++) {
            if (tab[a][b] == 0) zeros++;
            if (tab[a][b] > best) { best = tab[a][b]; bestA = a; bestB = b; }
        }

    if (csv) {
        printf("rounds,%d\nzeros,%d\npeak,%d\npeakN,%d\npeakD,%d\n",
               rounds, zeros, best, NS[bestA], DS[bestB]);
        for (int a = 0; a < 5; a++) {
            printf("n%d", NS[a]);
            for (int b = 0; b < 7; b++) printf(",%d", tab[a][b]);
            printf("\n");
        }
        return 0;
    }

    printf("每格 %d 轮，看「四连通 ≠ 八连通」出现几次（行 = 边长 n，列 = 水的密度）：\n\n", rounds);
    printf("        ");
    for (int b = 0; b < 7; b++) printf("%7d%%", DS[b]);
    printf("\n");
    for (int a = 0; a < 5; a++) {
        printf("  n=%2d  ", NS[a]);
        for (int b = 0; b < 7; b++) printf("%8d", tab[a][b]);
        printf("\n");
    }
    printf("\n  这张表的形状：**沿 n 单调上升，沿密度是单峰**（峰在 30%%~50%%）。\n");
    printf("     最高的一格：n = %d、密度 %d%%，%d / %d。\n", NS[bestA], DS[bestB], best, rounds);
    printf("     最低的那几格**全在 n 最小的那一行的两端**：n = 3 密度 5%% 只有 %d / %d，\n", tab[0][0], rounds);
    printf("     n = 3 密度 95%% 是 **精确的 0**（全表一共 %d 个 0）。\n", zeros);
    printf("\n  ⚠ 我一开始只扫了密度、把 n 固定在 30，得出的结论是「两头都掉到 0」——\n");
    printf("     **当场被实测打回来**：那张表上低密度那头是 192/200，一点没掉。\n");
    printf("     真正管事的不是密度，是 **W 的个数（≈ n² × 密度）**：\n");
    printf("     格子多，哪怕密度低，也有的是「只斜着挨着」的一对。\n");
    printf("\n  ⇒ **抓获率是一张曲面，不是一个数**，而它有两个旋钮 ——\n");
    printf("    顺手写的对拍生成器把两个都随手定了，而且 n 那一个几乎总是定在最小的一头。\n");
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

每格 200 轮，看「四连通 ≠ 八连通」出现几次（行 = 边长 n，列 = 水的密度）：

	5%	15%	30%	50%	70%	85%	95%
`n = 3`	3	22	50	64	44	16	★ 0
`n = 5`	16	64	131	159	95	28	2
`n = 8`	35	153	192	197	139	36	7
`n = 15`	112	199	★ 200	200	189	50	4
`n = 30`	193	200	200	200	200	112	6

★★★ 沿 n 单调上升，沿密度是单峰 —— 而最低的那几格全在 n 最小的那一行

沿 n：格子越多，越容易出现「一对 W 只斜着挨着」⇒ 抓获率单调上升（⚠ 精确地说：密度 ≤ 85% 的六列都单调，只有 95% 那一列例外 —— 那一列是 0 / 2 / 7 / 4 / 6，数太小，看不出单调。这条也是跑出来才改准的）；
沿密度：太稀（每个 W 都孤立）和太密（连成一整片）两头都抓不到，峰在 30%~50%；
⇒ 最低的几格全挤在 n = 3 那一行的两端：密度 5% 只有 3 / 200，密度 95% 是 ★ 精确的 0。

⚠ 而顺手写的对拍生成器，n 那个旋钮几乎总是定在最小的一头 （这本书前面十二轮解析里，生成器的 n 上限清一色是 10 到 15）。

⚠ 我第一版的结论是错的，而且是被实测打回来的

我最初只扫了密度一个旋钮、把 n 固定在 30，写下的结论是「两头都掉到 0，是一条单峰曲线」。

跑出来第一行就是 192 / 200 —— 低密度那头一点都没掉。

★ 原因：真正管事的不是密度，是 W 的个数（≈ n² × 密度）。 30 × 30 的网格里就算只有 5% 的水，也有 45 个 W，「一对只斜着挨着」的组合有的是。

⇒ ★★★ 触发条件也要量，不能推。 这本书上一次栽在同一件事上，是 P1104（推了个 49、实测 30）—— 那次错的是一个数，这次错的是结论的形状。

4★ 第 ② 条路：BFS —— 而它在这道题上是「将来才用得上」

p1596Bfs.cpp★ BFS（队列），八连通

// P1596 ★ 第 ② 条路：BFS（队列），八连通
//
// 和 DFS 版数出来的是同一个数 —— 留它在这儿有两个理由：
//   ① **验算走一条不一样的路**（第 7 章 P1147 那条）；
//   ② ★ 更实在的一条：**DFS 的递归深度 = 最大连通块的格子数**。
//      这道题 n, m <= 100 ⇒ 最多 10⁴ 层，离爆栈还很远；
//      可只要题目把 n 放到 10³ 量级（10⁶ 个格子），递归版就该换成 BFS 了。
//      ⇒ **「能不能用递归」是一道算术题，答案跟着 n 走。**
//
// ⚠ 标记要在**入队时**打，不是出队时 —— 出队才标记会让同一个格子被塞进队列好几次。

#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[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
static const int DY[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

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;
    vector<pair<int, int>> q;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (g[i][j] != 'W' || vis[i][j]) continue;
            cnt++;
            q.clear();
            q.push_back({i, j});
            vis[i][j] = true;               // ★ 入队就标记
            for (size_t h = 0; h < q.size(); h++) {
                auto [x, y] = q[h];
                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] != 'W' || vis[nx][ny]) continue;
                    vis[nx][ny] = true;
                    q.push_back({nx, ny});
                }
            }
        }
    printf("%d\n", cnt);
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

四档 × 300 轮，它和 DFS 版逐字节相同（0 / 1200 不一致）。

★ 留它在这儿的两个理由

验算走一条不一样的路（第 7 章 P1147 那条）；
★ 更实在的一条：DFS 的递归深度 = 最大连通块的格子数。这道题 N, M ≤ 100 ⇒ 最多 10⁴ 层，安全；可只要题目把 N 放到 10³ 量级（10⁶ 个格子），递归版就该换成 BFS 了。 ⇒ 「能不能用递归」是一道算术题，答案跟着 N 走。

⚠ 另外：BFS 的标记要在入队时打，不是出队时 —— 出队才标记会让同一个格子被塞进队列好几次。

5生成器：只有一个旋钮，而这一页整页都在说它

p1596Gen.cpp生成器：密度可调

// 数据生成器（P1596 对拍用）：`./p1596Gen <seed> [density] [n] [m]`
//
//   density 是**每个格子是水的概率的百分数**（默认 30）。
//
// ★ 这个生成器只有一个旋钮，而这一页整页都在说那个旋钮：
//   「四连通写成八连通」这个 bug 的抓获率，**随密度先升后降，两头都是精确的 0**：
//     · 密度很低 ⇒ 每个 W 都孤立 ⇒ 四连通和八连通都等于 W 的个数，**一样**；
//     · 密度很高 ⇒ 连成一大片 ⇒ 两边都是 1，**还是一样**。
//   ⇒ 曲线见 p1596Count.cpp。**顺手挑的那个密度落在哪儿，决定你抓不抓得到。**

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

    printf("%d %d\n", n, m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) putchar(ri(1, 100) <= density ? 'W' : '.');
        putchar('\n');
    }
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

生成器造 n, m ≤ 12 的随机网格（这是本书前十二轮解析的默认尺寸），只有密度可调：

密度	⚠ `p1596Four` 被抓	`p1596Bfs` 不一致
5%	41 / 300	0
30%	211 / 300	0
60%	209 / 300	0
90%	★ 20 / 300	0

⇒ 同一个 bug、同一份生成器，只把密度从 30% 改成 90%，抓获率掉到十分之一。

6一张总表

版本	做法	样例	密度 30% × 300 轮	密度 90% × 300 轮	结果
⚠ `p1596Four`	照搬四连通	✗ 13	✗ 抓 211	✗ 抓 20	✗ WA
★ `p1596Bfs`	BFS，八连通	✓ 3	✓	✓	★ AC
★ `p1596`	DFS，八连通	✓ 3	✓	✓	★ AC

这一页记住三句话

★★★ 抓获率是一张曲面，不是一个数 —— 它有两个旋钮（网格边长 n、水的密度）。沿 n 单调上升，沿密度是单峰；最低的那几格全在 n 最小的那一行的两端。 ⚠ 而顺手写的对拍生成器，n 那个旋钮几乎总是定在最小的一头。
★★★ 触发条件也要量，不能推。 我第一版只扫了密度、把 n 固定在 30，写下「两头都掉到 0」—— 实测第一行就是 192/200。真正管事的是 W 的个数（≈ n² × 密度）。
★ 「能不能用递归」是一道算术题：DFS 的递归深度 = 最大连通块的格子数。这道题 10⁴ 层安全，N 再大一个量级就该换 BFS。

洛谷 P1596 [USACO10OCT] Lake Counting S

0题目原文（本地存了一份）

输入

输出

1和本章正文只差一个常量

2⚠ 那个错法：照搬四连通

3★★★ 抓获率是一张曲面，不是一个数

4★ 第 ② 条路：BFS —— 而它在这道题上是「将来才用得上」

5生成器：只有一个旋钮，而这一页整页都在说它

6一张总表