俄罗斯⽅块

题目描述

⼩杨同学⽤不同种类的俄罗斯⽅块填满了⼀个⼤⼩为 的⽹格图。 ⽹格图由 个带颜⾊⽅块构成。⼩杨同学现在将这个⽹格图交给了你，请你计算出⽹格图中俄罗斯⽅块的种类 数。 如果两个同⾊⽅块是四连通（即上下左右四个相邻的位置）的，则称两个同⾊⽅块直接连通；若两个同⾊⽅块同时 与另⼀个同⾊⽅块直接或间接连通，则称两个同⾊⽅块间接连通。⼀个俄罗斯⽅块由⼀个⽅块和所有与其直接或间 接连通的同⾊⽅块组成。定义两个俄罗斯⽅块的种类相同当且仅当通过平移其中⼀个俄罗斯⽅块可以和另⼀个俄罗 斯⽅块重合；如果两个俄罗斯⽅块颜⾊不同，仍然视为同⼀种俄罗斯⽅块。 例如，在如下情况中，⽅块 和⽅块 是同⼀种俄罗斯⽅块，⽽⽅块 和⽅块 不是同⼀种俄罗斯⽅块。 1 方块1： 方块2： 方块3： 2 1 1 1 2 2 2 1 3 1 1 2 2 1 1 4 1 1

输入格式

第⼀⾏包含两个正整数 ，表⽰⽹格图的⼤⼩。 对于之后 ⾏，第 ⾏包含 个正整数 ，表⽰该⾏ 个⽅块的颜⾊。

输出格式

输出⼀个⾮负整数，表⽰俄罗斯⽅块的种类数。 3.2.4 样例1 1 5 6 2 1 2 3 4 4 5 3 1 2 3 3 4 5 4 1 2 2 3 4 5 5 1 6 6 7 7 8 6 6 6 7 7 8 8 1 7 3.2.5 样例解释 种类型的俄罗斯⽅块如下： 1 类型1： 类型2： 类型3： 类型4： 类型5： 类型6： 类型7： 2 1 2 3 4 4 5 6 6 7 7 8 3 1 2 3 3 4 5 6 6 7 7 8 8 4 1 2 2 3 4 5 5 1 3.2.6 数据范围 子任务编 数据点占 特殊条件 号 比 所有的俄罗斯⽅块⼤⼩不超过 ，即均可以放置于 的⽹格 1 图中 所有的俄罗斯⽅块的形状均为 或 类型，其中 为任意 2 正整数 3 对于全部数据，保证有 ， 。 3.2.7 参考程序 1 #include 2 #include 3 #include 4 5 using namespace std; 6 7 const int N = 505; 8 9 int n, m; 10 int val[N][N]; 11 int vis[N][N]; 12 13 int xmin, xmax, ymin, ymax; 14 int posx[N * N], posy[N * N], cnt; 15 int idx[N * N]; 16 bool isend[3 * N * N]; 17 18 map <int, int> ch[3 * N * N]; 19 int root, ncnt; 20 int ans; 21 22 void dfs(int x, int y, int c) 23 { 24 if (x < 1 || x > n || y < 1 || y > m) 25 return; 26 if (vis[x][y]) 27 return; 28 if (val[x][y] != c) 29 return; 30 vis[x][y] = 1; 31 xmin = min(xmin, x), xmax = max(xmax, x); 32 ymin = min(ymin, y), ymax = max(ymax, y); 33 posx[++cnt] = x; 34 posy[cnt] = y; 35 dfs(x - 1, y, c); 36 dfs(x + 1, y, c); 37 dfs(x, y - 1, c); 38 dfs(x, y + 1, c); 39 } 40 41 void go(int &n, int v) 42 { 43 if (!ch[n].count(v)) 44 ch[n][v] = ++ncnt; 45 n = ch[n][v]; 46 return; 47 } 48 49 void work(int x, int y) 50 { 51 cnt = 0; 52 xmin = n, xmax = 1; 53 ymin = m, ymax = 1; 54 dfs(x, y, val[x][y]); 55 for (int i = 1; i <= cnt; i++) 56 idx[i] = (posx[i] - xmin) * (ymax - ymin + 1) + (posy[i] - ymin); 57 sort(idx + 1, idx + cnt + 1); 58 int cur = root; 59 int lascnt = ncnt; 60 go(cur, xmax - xmin + 1); 61 go(cur, ymax - ymin + 1); 62 for (int i = 1; i <= cnt; i++) 63 go(cur, idx[i]); 64 ans += (! isend[cur]); 65 isend[cur] = 1; 66 } 67 68 int main() 69 { 70 root = ++ncnt; 71 scanf("%d%d", &n, &m); 72 for (int i = 1; i <= n; i++) 73 for (int j = 1; j <= m; j++) 74 scanf("%d", &val[i][j]); 75 for (int i = 1; i <= n; i++) 76 for (int j = 1; j <= m; j++) 77 if (!vis[i][j]) 78 work(i, j); 79 printf("%d\n", ans); 80 return 0; 81 }

样例输入 #1

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

样例输出 #1

样例解释 #1

种类型的俄罗斯⽅块如下： 1 类型1： 类型2： 类型3： 类型4： 类型5： 类型6： 类型7： 2 1 2 3 4 4 5 6 6 7 7 8 3 1 2 3 3 4 5 6 6 7 7 8 8 4 1 2 2 3 4 5 5 1

数据范围

子任务编 数据点占 特殊条件 号 比 所有的俄罗斯⽅块⼤⼩不超过 ，即均可以放置于 的⽹格 1 图中 所有的俄罗斯⽅块的形状均为 或 类型，其中 为任意 2 正整数 3 对于全部数据，保证有 ， 。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。