GESP 题解库 / 7 级题解 / [GESP202403 七级] 俄罗斯方块 · 第 17 / 24 题
GESP202403 七级 · P10379 · 中等

俄罗斯方块

把网格里所有"同色四连通块"摘出来,按"平移能否重合"去重,统计不同形状的个数。

📊
n, m ≤ 500
网格规模
🔢
2.5 × 10⁵
格子总数上限
⚡
O(n·m log(n·m))
时间复杂度
🎯
洪水填充 + 形状归一化
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨用不同种类的俄罗斯方块填满了一个 n × m 的网格图,每个格子有颜色 a[i][j]。

若两个同色格子上下左右相邻,称它们直接连通;通过其他同色格子间接相连则称间接连通。一个俄罗斯方块由某个格子以及与之直接或间接连通的所有同色格子组成。

两个俄罗斯方块种类相同,当且仅当通过平移其中一个可以和另一个重合;如果两者颜色不同,仍然视为同一种俄罗斯方块。

求网格图中俄罗斯方块的种类数。

💡
人话翻译:分两步走。
第一步:把每个"同色四连通块"圈出来(洪水填充),颜色只是用来切块的,切完之后颜色就没用了。
第二步:只看形状——因为只允许平移,所以形状既不随位置变、也不随颜色变。把每个块的形状搬到"自己左上角对齐"的坐标系里,写成一串坐标,扔进 set 去重,set 的大小就是答案。

🔍 关键词提取

网格连通块洪水填充平移等价形状归一化set 去重

已知条件

项目说明
输入第一行 n, m;随后 n 行,每行 m 个正整数表示颜色
输出一个整数:俄罗斯方块的种类数
数据范围1 ≤ n, m ≤ 500,1 ≤ a[i][j] ≤ n × m
连通定义同色 + 四连通(上下左右四个方向)
等价定义只允许平移重合,颜色无关

需要解决的问题

02
思维导图
整理解题思路的全貌
🧩 形状归一化 → set 去重
🧠 两步走
第一步:洪水填充,切出每个同色连通块
第二步:把形状归一化后用集合去重
颜色只在第一步起作用
答案 = 不同形状的个数
🪣 洪水填充
遍历每个未访问的格子
同色且四相邻才能扩展
用显式栈做迭代,防爆栈
每个格子最多进栈一次 → O(n·m)
📐 平移归一化
记下块内最小行 r₀、最小列 c₀
每格换算成 (r − r₀, c − c₀)
这套坐标与块的位置无关
排序后拼成字符串当"形状指纹"
⚠️ 易错点
忘记"同色"限制,把不同色也连起来
递归 DFS 在 500 × 500 上爆栈
不做归一化,直接比较原始坐标
把旋转/镜像也当同一种(本题不允许)
03
样例手算推导
样例网格的逐块拆解

🧮 样例:5 × 6 网格,答案 7

网格长这样(行列都从 1 开始编号):

行1:  1 2 3 4 4 5
行2:  1 2 3 3 4 5
行3:  1 2 2 3 4 5
行4:  1 6 6 7 7 8
行5:  6 6 7 7 8 8

先按颜色 + 四连通切块,一共切出 8 个块,再把每块的形状搬到左上角对齐的位置:

颜色块内的格子(行, 列)格子数归一化后的形状(行偏移, 列偏移)形状叫法
1(1,1) (2,1) (3,1) (4,1)4(0,0) (1,0) (2,0) (3,0)竖着的 1 × 4 长条
2(1,2) (2,2) (3,2) (3,3)4(0,0) (1,0) (2,0) (2,1)竖 3 格,右下伸出一格(L 形)
3(1,3) (2,3) (2,4) (3,4)4(0,0) (1,0) (1,1) (2,1)台阶形(Z 形)
4(1,4) (1,5) (2,5) (3,5)4(0,0) (0,1) (1,1) (2,1)横 2 格,下方左侧伸出一列(J 形)
5(1,6) (2,6) (3,6)3(0,0) (1,0) (2,0)竖着的 1 × 3 长条
6(4,2) (4,3) (5,1) (5,2)4(0,1) (0,2) (1,0) (1,1)横 2 + 下方左移一格(S 形)
7(4,4) (4,5) (5,3) (5,4)4(0,1) (0,2) (1,0) (1,1)与 6 号完全相同
8(4,6) (5,5) (5,6)3(0,1) (1,0) (1,1)3 格的 L 形(缺左上角)

8 个块里,6 号与 7 号形状一模一样 → 不同形状一共 7 种 ✓

1
为什么 6 号和 7 号是同一种?

6 号的格子:行 4 列 2、行 4 列 3、行 5 列 1、行 5 列 2

最小行 = 4,最小列 = 1,全部减掉后:

(0,1) (0,2) (1,0) (1,1)

7 号的格子:行 4 列 4、行 4 列 5、行 5 列 3、行 5 列 4

最小行 = 4,最小列 = 3,全部减掉后还是:

(0,1) (0,2) (1,0) (1,1)

两者颜色不同(6 和 7)、位置不同,但形状指纹完全一致

✅ 同一种,只算一次

2
3 号和 4 号看起来很像,为什么算两种?

3 号归一化后:(0,0) (1,0) (1,1) (2,1)

4 号归一化后:(0,0) (0,1) (1,1) (2,1)

3 号的横向包裹在"行跨度 0 ~ 2"里,

4 号的横向包裹在"行跨度 0 ~ 2、列跨度 0 ~ 1"但形状朝向不同

把 4 号平移、上下左右挪,都无法与 3 号重合

(4 号把 3 号沿主对角线翻了一下)

❌ 两种不同的形状

3
8 号为什么不和 3 号并入一种?

8 号只有 3 个格子:(0,1) (1,0) (1,1)

3 号有 4 个格子

格子数都不一样,形状怎么可能相同

❌ 是独立的一种

🔑
归一化的本质是"平移"这一种变换:平移只改变位置,不改变"格子之间的相对关系"。所以把整块减掉最小行、最小列,就得到了与位置无关的标准坐标。
排序是为了让同一组坐标只有一种写法(否则 (0,1)(1,0) 和 (1,0)(0,1) 会被当成两个不同的串)。
如果题目允许旋转,就得枚举 4 种旋转、取字典序最小的那个指纹;本题只允许平移,所以只用减法 + 排序。

🧮 反例:不做归一化 / 忘了"同色"会怎样

下面两行数据可以检验你的实现:

数据正确做法错误做法
2 3
1 2 3
1 2 3
三个 1 × 2 的竖块,颜色各不相同,答案是 1若按颜色分别统计,会得到 3(错)
2 2
1 2
3 4
四个孤立的单格,全是同一种 1 × 1,答案是 1若直接比较原坐标,会得到 4(错)
⚠️
两个高频错误:① 把颜色当成种类的一部分 —— 题目明确说"颜色不同仍视为同一种",颜色只用于切块;
② 直接拿原始坐标比较 —— 那样"形状相同但位置不同"的块会被判成不同种类,必须做平移归一化。
另外注意:旋转和镜像都不算同一种,不要自作主张地"取最小的旋转指纹"。
04
解法对比
连通块 + set 去重 vs 并查集 + 两两比对

⚔️ 解法对比

🟢 洪水填充 + 形状归一化 + set(推荐) 推荐

栈迭代 BFS/DFS 收集每个连通块,归一化排序后序列化成字符串,塞进 set

  • 时间 O(n·m log(n·m))
  • 每格进出栈一次,工作量线性
  • 代码约 40 行
  • set 天然去重,不用手写两两比较
💡
为什么用字符串而不是坐标数组当 key:C++ 的 set 支持 string 做元素,而 vector<pair<int,int>> 需要额外写比较器。
把坐标拼成 "r,c;" 形式的字符串,既好写又天然可比较;字符串长度正比于块大小,总长度是 O(n·m)。

🟠 并查集 + 形状两两比较

并查集合并同色相邻格子,再把每两个形状搬在一起试着重合

  • 时间 O(n·m α + K² · s)
  • K 是块数,s 是平均块大小
  • 代码约 55 行
  • 比较逻辑要手写,容易漏情况
⚠️
什么时候还行:块数很少时(比如子任务里块都很小)两两比较也能过。
但最坏情况不划算:如果网格被切成上万个块,K² 会瞬间爆炸,而 set 的做法依然是一次线性扫描加若干次小块内排序。

📈 性能对比

方案复杂度代码量
连通块 + 归一化 + setO(n·m log(n·m))约 40 行
并查集 + 形状两两比较O(n·m α + K² · s)约 55 行
直接比较原始坐标——❌ 位置不同的同型块会被判成不同
05
算法流程图
洪水填充 → 归一化 → set 去重
开始读入 n, m 与整个网格扫描每个尚未访问的格子 (i, j)从 (i, j) 出发做栈迭代洪水填充,收集同色四连通的所有格子求块内最小行 r₀ 与最小列 c₀,把每格换算成 (r − r₀, c − c₀) 并排序把排序后的坐标拼成字符串 key,插入 set网格里还有没访问的格子吗?有 ✓回到扫描,继续切下一个连通块没有了 ✗切块结束,进入输出输出 set 的大小(种类数)继续找下一个连通块
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🧩 俄罗斯方块种类统计

第一行 n m,随后 n 行每行 m 个颜色。程序切出所有同色四连通块,给出每个块的归一化形状与种类编号,并输出去重后的种类数。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(洪水填充 + 形状指纹去重)

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

int n, m;
int a[505][505];
bool vis[505][505];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

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

    set<string> kinds;                   // 形状指纹集合(自动去重)

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vis[i][j]) continue;

            // ---- 洪水填充:栈迭代收集同色四连通块 ----
            vector<pair<int,int>> cells;
            vector<pair<int,int>> stk;
            stk.push_back({i, j});
            vis[i][j] = true;

            while (!stk.empty()) {
                pair<int,int> cur = stk.back(); stk.pop_back();
                cells.push_back(cur);
                for (int d = 0; d < 4; d++) {
                    int x = cur.first  + dx[d];
                    int y = cur.second + dy[d];
                    if (x < 0 || x >= n || y < 0 || y >= m) continue;
                    if (vis[x][y]) continue;
                    if (a[x][y] != a[i][j]) continue;   // 必须同色
                    vis[x][y] = true;
                    stk.push_back({x, y});
                }
            }

            // ---- 平移归一化:整体减去块内最小行、最小列 ----
            int r0 = INT_MAX, c0 = INT_MAX;
            for (auto &p : cells) {
                r0 = min(r0, p.first);
                c0 = min(c0, p.second);
            }
            vector<pair<int,int>> rel;
            for (auto &p : cells)
                rel.push_back({p.first - r0, p.second - c0});

            // ---- 排序后序列化成字符串,作为"形状指纹" ----
            sort(rel.begin(), rel.end());
            string key;
            for (auto &p : rel) {
                key += to_string(p.first) + "," + to_string(p.second) + ";";
            }
            kinds.insert(key);
        }
    }

    printf("%d\n", (int)kinds.size());
    return 0;
}
🔑
为什么"排序 + 拼字符串"能代表形状?两个块平移重合,意味着它们的格子相对位置完全一致,归一化之后就是同一个坐标集合。
集合本身没有"顺序",而字符串有 —— 所以先把坐标按 (行, 列) 排序,每个集合就只剩下唯一一种写法,此时"集合相等"与"字符串相等"完全等价。
(这就是"序列化"的常用套路,树的最小表示、状态哈希都用同一招。)

📖 关键几行怎么看

代码作用为什么这样写
if (a[x][y] != a[i][j]) continue;同色限制只有同色才连通;a[i][j] 是整块的颜色
stk.push_back({i, j});迭代填充显式栈代替递归,2.5 × 10⁵ 个格子也不爆栈
r0 = min(r0, p.first);找最小行列平移归一化的基准点
rel.push_back({p.first - r0, p.second - c0});搬到左上角坐标只保留"相对位置"
sort(rel.begin(), rel.end());固定写法让同一个集合只有一种序列化结果
kinds.insert(key);去重统计重复指纹自动被忽略,最后 size() 就是答案
⚠️
五个坑:① 忘了判断同色,把相邻的不同色格子当成一块;② 用递归 DFS,在 500 × 500 的大连通块上爆栈;③ 不排序就拼串,(0,1)(1,0) 与 (1,0)(0,1) 会被当成两个形状;④ 忘了归一化,直接拿原坐标拼串;⑤ 自作主张把"旋转/镜像"也算同一种 —— 题目只允许平移。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5 6
1 2 3 4 4 5
1 2 3 3 4 5
1 2 2 3 4 5
1 6 6 7 7 8
6 6 7 7 8 8
7题面样例:8 个块中 6 号与 7 号同型
1 1
1
1只有一个格子:只有 1 种
2 3
1 2 3
1 2 3
1三个 1 × 2 竖块,颜色各不相同但形状一致
2 3
1 1 2
1 2 2
2一个 L 形与一个"反向 L 形":只允许平移,两者不重合
2 2
1 2
3 4
1四个孤立的单格,全部是 1 × 1 这一种
3 3
1 1 2
1 3 2
3 3 4
4L 形、竖 1 × 2、另一种 L 形、单格,共 4 种
3 4
1 1 1 2
3 3 1 2
3 3 4 4
4横 2 与竖 2 不是同一种(旋转不算同型)
✅
自查清单:① 洪水填充判断同色了吗?② 块内坐标减去最小行列了吗?③ 拼串前排序了吗?④ 用"三个不同色的竖块"这组数据验证过答案确实是 1 吗?

🚨 易错点清单

⚠️
忘记"同色"条件:只有同色且四相邻才属于同一个俄罗斯方块。
⚠️
不做平移归一化:直接比较原始坐标,位置不同的同型块会被判成不同种类。
⚠️
归一化后不排序:同一个坐标集合会有多种排列,字符串比较会失败。
⚠️
把旋转/镜像当成同一种:题目只允许平移重合,横向多米诺与竖向多米诺是两种形状。
⚠️
递归 DFS 爆栈:整个网格可能连成一块,深度可达 2.5 × 10⁵。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n·m log(n·m))
空间复杂度
O(n·m)
格子总数
最多 2.5 × 10⁵
填充部分
O(n·m)

时间怎么算的?

空间都用在哪?

网格数组 a 与访问标记 vis 各占 n × m;临时存一个块最多也只要 n × m,set 里所有指纹字符串的总长度是 O(n·m)。

✅ 2.5 × 10⁵ 个格子,一次线性扫描加若干次小块内排序,1 秒限制下非常轻松。本题的难点是"把平移等价翻译成字符串相等"这一层建模,代码本身只是两个模板(洪水填充 + 归一化)。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// ---- 模板 1:网格洪水填充(栈迭代,防爆栈)----
vector<pair<int,int>> stk{{i, j}};
vis[i][j] = true;
while (!stk.empty()) {
    auto cur = stk.back(); stk.pop_back();
    cells.push_back(cur);
    for (int d = 0; d < 4; d++) {
        int x = cur.first + dx[d], y = cur.second + dy[d];
        if (x < 0 || x >= n || y < 0 || y >= m) continue;
        if (vis[x][y] || a[x][y] != a[i][j]) continue;   // 同色 + 未访问
        vis[x][y] = true;
        stk.push_back({x, y});
    }
}

// ---- 模板 2:平移归一化(把"平移等价"变成"字符串相等")----
for (auto &p : cells) { r0 = min(r0, p.first); c0 = min(c0, p.second); }
vector<pair<int,int>> rel;
for (auto &p : cells) rel.push_back({p.first - r0, p.second - c0});
sort(rel.begin(), rel.end());
string key;
for (auto &p : rel) key += to_string(p.first) + "," + to_string(p.second) + ";";

// ---- 变换的扩展:指纹怎么升级 ----
// 只允许平移        → 减最小行列 + 排序(本题)
// 还允许旋转 90 度  → 枚举 4 种旋转,取字典序最小的指纹
// 还允许镜像翻转    → 再补 4 种,共 8 种变换取最小
// 允许任意形状相等  → 需要图同构级别的判定(本题不需要)

// ---- 洪水填充的 8 连通版本 ----
// int dx[8] = {1,-1,0,0,1,1,-1,-1};
// int dy[8] = {0,0,1,-1,1,-1,1,-1};

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
网格洪水填充切出每个"同色四连通块"岛屿数量、连通块计数、染色/区域问题
平移归一化把"平移等价"翻译成"字符串相等"图形去重、拼图判定、形状哈希
栈式迭代遍历避免 500 × 500 的连通块爆栈所有大规模网格/树的遍历
set 去重判重顺手完成,直接得到种类数字符串判重、状态去重、离散化
🌟
思考题:如果题目放宽成"旋转 90 度的整数倍后能重合就算同一种",需要怎么改?(提示:把归一化后的坐标集合分别做 4 次旋转,得到 4 个指纹,取其中字典序最小的那一个当代表。
再想一想:为什么"取最小的那一个"就足够了?因为"旋转后重合"本身就是一种等价关系,同一类里所有块的最小指纹必然相同。)