NOIP2014普及组复赛试题 螺旋矩阵三种不同解答
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<cstdio>
using namespace std;
bool pd(int,int) ;
int i,j;
bool p;
int main()
{
int n,x,y,u,d,l,r,tot=0; // U为上边界,D为下边界 ,L为左边界,R为右边界;
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%d%d%d",&n,&i,&j);
d=n;r=n;u=1;l=1; //各边界赋初值;
x=1;y=0;
p=true;
while((tot<n*n)&&p)
{
while((y<r)&&p){++y;++tot;pd(x,y);}--r;//在上侧边界上向右移动,当上侧一行的结束时,控制其右边界向左缩一列;
while((x<d)&&p){++x;++tot;pd(x,y);}--d;//在右侧边界上向下移动,当右侧一列的结束时,控制其下边界向上缩一行;
while((y>l)&&p){--y;++tot;pd(x,y);}++l;//在下侧边界上向左移动,当下侧一行的结束时,控制其左边界向右缩一列;
while((x>u+1)&&p){--x;++tot;pd(x,y);}++u;//在左侧边界上向上移动,当左侧一列的结束时,控制其上边界向下缩一行;
}
printf("%d\n",tot);
NOIP2014普及组复赛试题解答2_IT认证_资格考试/认证_教育专区。NOIP2014普及组复赛试题 螺旋矩阵 解答NOIP2014 普及组复赛试题解答 3. 螺旋矩阵 【问题描述】 一...
NOIP2014普及组复赛试题解答_学科竞赛_初中教育_教育专区 暂无评价0人阅读0次下载举报文档 NOIP2014普及组复赛试题解答_学科竞赛_初中教育_教育专区。NOIP2014...
noip2014普及组复赛题解_财会/金融考试_资格考试/...螺旋矩阵 没一圈的数量有规律的,最外面一圈(n-1... 科目三实际道路驾驶考试注意事项 驾考新题抢先版...
( NOIP2014)复赛 普及组(请选手务必仔细阅读本页内容)一.题目概况中文题目名称...螺旋矩阵 matrix matrix matrix.in matrix.out 1秒 10 10 有 传统 128M 子...
noip2014普及组初赛试题_学科竞赛_初中教育_教育专区。noip2014普及组初赛试题第二十届全国青少年信息学奥林匹克联赛初赛普及组 pascal 语言试题 1、以下哪个是面向...
noip2014普及组复赛解题报告1. 珠心算测验 穷举+桶...3. 螺旋矩阵 由于 1 ≤ n ≤ 30,000,所以我们... 推理型题分析与总结 78份文档 一起来学广场舞 ...
控制线 D. 系统文件 断电后会丢失数据的存储器是( A. RAM B. ROM C. 硬盘 D. 光盘 CCF NOIP2014 初赛普及组 C 语言试题 第 1 页,共 8 页 8. 以下...
NOIP2014初赛普及组试题_C++_学科竞赛_初中教育_教育专区。NOIP2014初赛普及组...(最大子矩阵和)给出 m 行 n 列的整数矩阵,求最大的子矩阵和(子矩阵不能...
控制线 D. 系统文件 断电后会丢失数据的存储器是( A. RAM B. ROM C. 硬盘 D. 光盘 CCF NOIP2014 初赛普及组 C 语言试题 第 1 页,共 8 页 8. 以下...
控制线 D. 系统文件 断电后会丢失数据的存储器是( A. RAM B. ROM C. 硬盘 D. 光盘 CCF NOIP2014 初赛普及组 C++语言试题 第 1 页,共 8 页 8. 以下...
热门文档