NOIP2014普及组复赛 螺旋矩阵
更新时间:2023-10-20 12:36:01 阅读量: 综合文库 文档下载
NOIP2014普及组复赛试题解答
3. 螺旋矩阵 【问题描述】
一个n 行n列的螺旋矩阵可由如下方法生成:
从矩阵的左上角(第1行第1列)出发,初始时向右移动:如果前方是未曾经过的格子,则继续前进,否则右转;重复上述操作直至经过矩阵中所有格子。根据经过顺序,在格子中依次填入1,2,3,…,n2,便构成了一个螺旋矩阵。
现给出矩阵大小n以及i和j,请你求出该矩阵中第i行第j列的数是多少。 【分析】
这是个蛇形填数问题。 如果采用先枚举二维数组再找对应的元素方法,由于1 ≤ n ≤ 30,000,需要建立一个 30,000× 30,000的二维数组,结果会发生数据溢出且超出运行内存上限(128M)。
我们可以采用类似贪吃蛇的方法,让它在N×N个方格内自外向内逐格移动,控制其向右转的方向,并计算其长度。
解法一
#include
int n,x,y,u,d,l,r,tot=0; // U为上边界,D为下边界 ,L为左边界,R为右边界;
freopen(\freopen(\scanf(\
d=n;r=n;u=1;l=1; //各边界赋初值; x=1;y=0; p=true;
while((tot while((y while((x while((y>l)&&p){--y;++tot;pd(x,y);}++l;//在下侧边界上向左移动,当下侧一行的结束时,控制其左边界向右缩一列; while((x>u+1)&&p){--x;++tot;pd(x,y);}++u;//在左侧边界上向上移动,当左侧一列的结束时,控制其上边界向下缩一行; } printf(\ fclose(stdin);fclose(stdout); return 0; } bool pd(int x,int y) //判断是否到达目的地,如果到达则停止枚举; { if((x==i)&&(y==j))p=false; return p; } 解法二: 在上一个解法中,如果遇到极端情况时,可能需要枚举达900000000次,这显然太慢了些,我们可以根据贪吃移动的特点对程序进行优化。 可以这样考虑,当贪吃蛇到每个行列的转折点时,可以先判断目的地是否在自己的正前方,如果是则只需计算当前位置到目的地的距离加上自身的长度即可;否则就计算到下一个转折点人距离,加上当前自身长度,并到达下一个转折点,同时控制所在行(或列)的边界向内侧移动; #include int n,i,j,x,y,u,d,l,r,tot=1; // U为上边界,D为下边界 ,L为左边界,R为右边界; freopen(\freopen(\scanf(\ d=n;r=n;u=1;l=1; //各边界赋初值; x=1;y=1; bool p=true; while(p) { if(p) if(x==i) //在上侧边界线上向右移动。如果目的地在正前方,则当前长度加上当前位置到目的地距离,结束循环; {tot=tot+j-y;p=false;} else //否则,当前长度加当前位置至行未的长度,同时到达右边界位置,并控制其上边界向下移动一列; {tot=tot+r-y;y=r;++u;} if(p) if(y==j) {tot=tot+i-x;p=false;} else {tot=tot+d-x;x=d;--r; } if(p) if(x==i) {tot=tot+y-j;p=false;} else {tot=tot+y-l;y=l;--d; } if(p) if(y==j) {tot=tot+x-i;p=false;} else {tot=tot+x-u;x=u;++l;} } printf(\ fclose(stdin);fclose(stdout); return 0; } 解法三: 对解法二,我们还可以进行优化。考虑到贪吃蛇总是从外围一圈圈地向目的地前进,而每一圈刚好是一个正方形,我们可以先计算外围各圈正方形的周长之和,再让贪吃蛇从目的地所在圈的左上角出发,计算其从出发地到目的地的长度就可以了。 #include int n,i,j,x,y,u,d,l,r,k,t,tot=0; // U为上边界,D为下边界 ,L为左边界,R为右边界; bool p=true; freopen(\ freopen(\ scanf(\ x=i u=k;l=k;d=n-k+1;r=n-k+1; //设定各边界; for(t=1;t {tot=tot+(n-1)*4;n=n-2;} //计算在到达目的地外围所有圈的周长之和; x=k;y=k;++tot; //进入目的地所在的那一圈,初始化出发地; if(p) if(x==i) //向右移动。如果目的地在正前方,则当前长度加上当前位置到目的地距离,结束循环; {tot=tot+j-y;p=false;}
正在阅读:
NOIP2014普及组复赛 螺旋矩阵10-20
2017年中国大输液市场调研及发展现状分析(目录) - 图文04-30
江西省高考数学试卷理科04-07
高中地理第一章第一节宇宙中的地球教案6新人教版必修105-05
2012年第二十二届全国初中应用物理竞赛试题 - 图文09-28
开题报告内容及要求(中北大学)03-17
国家助学贷款政策知识问答06-18
广东省质量技术监督举报特种设备安全违法行为奖励办法01-29
镇党委议事规则11-17
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 复赛
- 矩阵
- 螺旋
- 普及
- NOIP2014
- AETOS艾拓思:个人投资者在汇市上的生存之道
- 安益238号渝南资产应收账款投资(一期)信托计划
- 2016-2020年中国城市燃气行业深度调研及投资前景预测报告 - 图文
- 诵读比赛主持词
- 从\\"Made in China\\"到\\"Design in China\\"
- 新编日语(1至4册)-语法
- 晶体学习题
- 数据结构顺序表的实现
- 南林 - 图文
- 塔机检测试题-选择题答案
- 关于将环洞庭湖生态经济圈纳入国家发展战略的提案
- 精品解析:【市级联考】江苏省苏州市2019届高三高考模拟最后一卷数学试题(原卷版) -
- 盾构机吊装专项方案终结版
- 西安理工大学硕士材料科学基础真题2009年
- 小学语文六年级句子练习
- 中心对称图形教案
- Splunk部署手册0422 v2.0
- 新木马屠城记之微软收购诺基亚
- 化工杯--题库
- 2015年度分包单位安全生产责任书- 合并