欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：[P10379 GESP202403 七级] 俄罗斯方块 - 洛谷
【题目描述】
小杨同学用不同种类的俄罗斯方块填满了一个大小为n × m n \times mn×m的网格图。
网格图由n × m n \times mn×m个带颜色方块构成。小杨同学现在将这个网格图交给了你，请你计算出网格图中俄罗斯方块的种类数。
如果两个同色方块是四连通（即上下左右四个相邻的位置）的，则称两个同色方块直接连通；若两个同色方块同时与另一个同色方块直接或间接连通，则称两个同色方块间接连通。一个俄罗斯方块由一个方块和所有与其直接或间接连接的同色方块组成。定义两个俄罗斯方块的种类相同当且仅当通过平移其中一个俄罗斯方块可以和另一个俄罗斯方块重合；如果两个俄罗斯方块颜色不同，仍然视为同一种俄罗斯方块。
例如，在如下情况中，方块1 11和方块2 22是同一种俄罗斯方块，而方块1 11和方块3 33不是同一种俄罗斯方块。
【输入】
第一行包含两个正整数n nn和m mm，表示网格图的大小。
对于之后的n nn行，第i ii行包含m mm个正整数a i 1 , a i 2 , … a i m a_{i1}, a_{i2}, \dots a_{im}ai1,ai2,…aim，表示该行m mm个方块的颜色。
【输出】
输出一行一个整数表示答案。
【输入样例】
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【算法标签】
《洛谷 P10379 俄罗斯方块》 #模拟# #搜索# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=505;intn,m,k,s,t,sx,sy;// n,m: 网格大小, sx,sy: 当前连通块的起始点inta[N][N];// 存储网格中的值intans;// 结果，不同形状的数量intvis[N][N];// 访问标记数组// 四个方向的偏移量：右、下、左、上intd[4][2]={{0,1},{1,0},{0,-1},{-1,0}};vector<pair<int,int>>e;// 存储当前连通块中所有点的相对坐标set<vector<pair<int,int>>>se;// 存储所有不同形状的连通块// 深度优先搜索，用于寻找连通块voiddfs(intx,inty){// 将当前点的相对坐标（相对于连通块起始点）存入向量ee.push_back({x-sx,y-sy});// 标记当前点已访问vis[x][y]=1;// 遍历四个方向for(inti=0;i<4;i++){intxx=x+d[i][0];// 新的x坐标intyy=y+d[i][1];// 新的y坐标// 检查新坐标是否有效if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&// 在网格范围内a[xx][yy]==a[x][y]&&// 值相同!vis[xx][yy])// 未访问过{dfs(xx,yy);// 继续深度优先搜索}}}intmain(){// 输入网格大小cin>>n>>m;// 输入网格数据for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){cin>>a[i][j];}}// 遍历整个网格for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){// 如果当前点未访问过if(!vis[i][j]){// 记录连通块的起始点sx=i;sy=j;// 从当前点开始深度优先搜索，找到整个连通块dfs(i,j);// 将当前连通块的形状（相对坐标向量）插入集合// 集合会自动去重se.insert(e);// 清空向量，为下一个连通块做准备e.clear();}}}// 输出不同形状的数量cout<<se.size()<<endl;return0;}【运行结果】
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
