企业官网建设流程全解析

国内大一html网站简单设计,剑灵网站模板,wordpress 两个数据库 互通,俄语网站都哪些2024年3月GESP真题及题解(C七级): 俄罗斯方块 题目描述 小杨同学用不同种类的俄罗斯方块填满了一个大小为 n m n \times m nm 的网格图。 网格图由 n m n \times m nm 个带颜色方块构成。小杨同学现在将这个网格图交给了你#xff0c;请你计算出网格图中俄罗斯方块的种类…2024年3月GESP真题及题解(C七级): 俄罗斯方块题目描述小杨同学用不同种类的俄罗斯方块填满了一个大小为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个方块的颜色。输出格式输出一行一个整数表示答案。输入输出样例 1输入 15 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输出 17说明/提示子任务分数n , m ≤ n,m \leqn,m≤特殊约定1 1130 303020 2020所有俄罗斯方块大小不超过5 × 5 5 \times 55×52 2230 3030500 500500所有俄罗斯方块大小均为1 × x 1 \times x1×x或x × 1 x \times 1x×1类型其中x xx是任意正整数3 3340 4040500 500500无对全部的测试数据保证1 ≤ n , m ≤ 500 1 \leq n, m \leq 5001≤n,m≤5001 ≤ a i , j ≤ n × m 1 \leq a_{i,j} \leq n \times m1≤ai,j​≤n×m。思路分析核心思路统计网格中不同形状的连通块数量。关键点在于通过相对坐标和标准化来识别形状忽略颜色差异和位置平移。算法流程读取网格存储颜色值遍历每个未访问的格子发现新连通块起点DFS搜索连通块标记已访问存储每个点相对于起点的坐标相对坐标形状标准化对相对坐标排序消除遍历顺序影响去重计数使用set自动去重最终set大小为不同形状数代码实现#includebits/stdc.husingnamespacestd;constintN505;intn,m;inta[N][N];// 网格颜色intvs[N][N];// 访问标记intdx[4]{-1,1,0,0};// 上下左右intdy[4]{0,0,-1,1};// 当前连通块信息intsx,sy;// 连通块起点vectorpairint,intblock;// 相对坐标集合/** * DFS搜索同色连通块 * color 当前连通块颜色 * x,y 当前位置 * 功能收集连通块所有点的相对坐标相对于起点 */voiddfs(intcolor,intx,inty){vs[x][y]1;// 存储相对坐标当前点-起点block.push_back({x-sx,y-sy});// 四方向搜索for(inti0;i4;i){intnxxdx[i];intnyydy[i];// 边界检查、同色检查、未访问检查if(nx1nxnny1nyma[nx][ny]color!vs[nx][ny]){dfs(color,nx,ny);}}}intmain(){cinnm;// 读入网格for(inti1;in;i)for(intj1;jm;j)cina[i][j];memset(vs,0,sizeof(vs));setvectorpairint,ints;// 形状集合自动去重// 遍历所有格子for(inti1;in;i){for(intj1;jm;j){if(!vs[i][j]){// 发现新连通块sxi;syj;// 设置起点block.clear();dfs(a[i][j],i,j);// 搜索连通块// 标准化排序确保相同形状有相同表示sort(block.begin(),block.end());s.insert(block);// 自动去重}}}couts.size()endl;// 不同形状数量return0;}功能分析核心功能判断两个连通块是否为同一种类通过平移可以重合。关键技术点相对坐标表示// 存储相对坐标而非绝对坐标block.push_back({x-sx,y-sy});这样不同位置的相同形状会有相同的相对坐标集合自动处理了平移等价性形状标准化sort(block.begin(),block.end());消除DFS遍历顺序的影响确保相同形状的连通块有完全相同的坐标序列自动去重setvectorpairint,ints;利用set自动去除重复形状每个形状表示为排序后的相对坐标向量时间复杂度DFS部分O(n×m)每个格子访问一次排序部分每个连通块内部排序总复杂度O(klogk)k为连通块总大小总体复杂度在网格大小500×500范围内可接受空间复杂度存储网格O(n×m)DFS递归栈最坏O(n×m)形状存储O(形状数×平均大小)各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}