【题目来源】https://www.luogu.com.cn/problem/P10379【题目描述】小杨同学用不同种类的俄罗斯方块填满了一个大小为 n×m 的网格图。网格图由 n×m 个带颜色方块构成。小杨同学现在将这个网格图交给了你请你计算出网格图中俄罗斯方块的种类数。如果两个同色方块是四连通即上下左右四个相邻的位置的则称两个同色方块直接连通若两个同色方块同时与另一个同色方块直接或间接连通则称两个同色方块间接连通。一个俄罗斯方块由一个方块和所有与其直接或间接连接的同色方块组成。定义两个俄罗斯方块的种类相同当且仅当通过平移其中一个俄罗斯方块可以和另一个俄罗斯方块重合如果两个俄罗斯方块颜色不同仍然视为同一种俄罗斯方块。……【输入格式】第一行包含两个正整数 n 和 m表示网格图的大小。对于之后的 n 行第 i 行包含 m 个正整数 a_i1,a_i2,…a_im表示该行 m 个方块的颜色。【输出格式】输出一行一个整数表示答案。【输入样例】5 61 2 3 4 4 51 2 3 3 4 51 2 2 3 4 51 6 6 7 7 86 6 7 7 8 8【输出样例】7【数据范围】对全部的测试数据保证 1≤n,m≤5001≤a_ij≤n×m。【算法分析】● norm() 函数的功能是将一组坐标点转换为一个唯一标识形状的字符串用于判断两个连通块是否形状相同。核心代码分析如下1找到最小坐标找到所有点中最小的行号和列号。int txv[0].first; int tyv[0].second; for(auto x:v) { txmin(tx,x.first); tymin(ty,x.second); }2平移归一化将所有坐标减去最小值使形状平移到原点附近。sto_string(x.first-tx),to_string(x.second-ty);;示例说明假设有两个形状相同的连通块形状A{(2,3), (2,4), (3,3)}形状B{(5,6), (5,7), (6,6)}经过归一化后都变成0,0;0,1;1,0;。其中逗号分隔同一坐标的行和列分号分隔不同的坐标点。●​​​​​​​ 为什么能去重setstring 会自动“递增无重”因为相同形状 → 归一化后的字符串完全相同不同形状 → 归一化后的字符串不同所以 st.insert(norm()) 只会保留不同形状的字符串表示最终 st.size() 就是不同形状的数量。【算法代码】#include bits/stdc.h using namespace std; const int N5e25; int a[N][N],g[N][N]; vectorpairint,int v; setstring st; int n,m; int dx[] {1,0,-1,0}; int dy[] {0,1,0,-1}; void dfs(int x,int y,int val) { v.push_back({x,y}); g[x][y]1; for(int i0; i4; i) { int txxdx[i],tyydy[i]; if(tx1 txn ty1 tym) { if(!g[tx][ty] a[tx][ty]val) dfs(tx,ty,val); } } } string norm() { int txv[0].first; int tyv[0].second; for(auto x:v) { txmin(tx,x.first); tymin(ty,x.second); } string s; for(auto x:v) { sto_string(x.first-tx),to_string(x.second-ty);; } return s; } int main() { cinnm; for(int i1; in; i) { for(int j1; jm; j) { cina[i][j]; } } for(int i1; in; i) { for(int j1; jm; j) { if(!g[i][j]) { v.clear(); dfs(i,j,a[i][j]); st.insert(norm()); } } } coutst.size(); return 0; } /* in: 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 out: 7 */【参考文献】https://www.luogu.com.cn/problem/solution/P10379https://gesp.ccf.org.cn/101/attach/1602047231131680.pdf