把网格里所有"同色四连通块"摘出来,按"平移能否重合"去重,统计不同形状的个数。
小杨用不同种类的俄罗斯方块填满了一个 n × m 的网格图,每个格子有颜色 a[i][j]。
若两个同色格子上下左右相邻,称它们直接连通;通过其他同色格子间接相连则称间接连通。一个俄罗斯方块由某个格子以及与之直接或间接连通的所有同色格子组成。
两个俄罗斯方块种类相同,当且仅当通过平移其中一个可以和另一个重合;如果两者颜色不同,仍然视为同一种俄罗斯方块。
求网格图中俄罗斯方块的种类数。
网格连通块洪水填充平移等价形状归一化set 去重
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n, m;随后 n 行,每行 m 个正整数表示颜色 |
| 输出 | 一个整数:俄罗斯方块的种类数 |
| 数据范围 | 1 ≤ n, m ≤ 500,1 ≤ a[i][j] ≤ n × m |
| 连通定义 | 同色 + 四连通(上下左右四个方向) |
| 等价定义 | 只允许平移重合,颜色无关 |
网格长这样(行列都从 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 种 ✓
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)、位置不同,但形状指纹完全一致
✅ 同一种,只算一次
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 号沿主对角线翻了一下)
❌ 两种不同的形状
8 号只有 3 个格子:(0,1) (1,0) (1,1)
3 号有 4 个格子
格子数都不一样,形状怎么可能相同
❌ 是独立的一种
下面两行数据可以检验你的实现:
| 数据 | 正确做法 | 错误做法 |
|---|---|---|
2 3 | 三个 1 × 2 的竖块,颜色各不相同,答案是 1 | 若按颜色分别统计,会得到 3(错) |
2 2 | 四个孤立的单格,全是同一种 1 × 1,答案是 1 | 若直接比较原坐标,会得到 4(错) |
栈迭代 BFS/DFS 收集每个连通块,归一化排序后序列化成字符串,塞进 set
set 支持 string 做元素,而 vector<pair<int,int>> 需要额外写比较器。并查集合并同色相邻格子,再把每两个形状搬在一起试着重合
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 连通块 + 归一化 + set | O(n·m log(n·m)) | 约 40 行 |
| 并查集 + 形状两两比较 | O(n·m α + K² · s) | 约 55 行 |
| 直接比较原始坐标 | —— | ❌ 位置不同的同型块会被判成不同 |
第一行 n m,随后 n 行每行 m 个颜色。程序切出所有同色四连通块,给出每个块的归一化形状与种类编号,并输出去重后的种类数。
点按钮开始 →
#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() 就是答案 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 6 | 7 | 题面样例:8 个块中 6 号与 7 号同型 |
1 1 | 1 | 只有一个格子:只有 1 种 |
2 3 | 1 | 三个 1 × 2 竖块,颜色各不相同但形状一致 |
2 3 | 2 | 一个 L 形与一个"反向 L 形":只允许平移,两者不重合 |
2 2 | 1 | 四个孤立的单格,全部是 1 × 1 这一种 |
3 3 | 4 | L 形、竖 1 × 2、另一种 L 形、单格,共 4 种 |
3 4 | 4 | 横 2 与竖 2 不是同一种(旋转不算同型) |
网格数组 a 与访问标记 vis 各占 n × m;临时存一个块最多也只要 n × m,set 里所有指纹字符串的总长度是 O(n·m)。
✅ 2.5 × 10⁵ 个格子,一次线性扫描加若干次小块内排序,1 秒限制下非常轻松。本题的难点是"把平移等价翻译成字符串相等"这一层建模,代码本身只是两个模板(洪水填充 + 归一化)。
// ---- 模板 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 去重 | 判重顺手完成,直接得到种类数 | 字符串判重、状态去重、离散化 |