螺旋矩阵题解

发布于 2018-12-06  838 次阅读


 

螺旋矩阵

(matrix.cpp)

【问题描述】

一个n行n列的螺旋矩阵可由如下方法生成:

从矩阵的左上角(第1行第1列)出发,初始时向右移动;如果前方是未曾经过的格子, 则继续前进,否则右转;重复上述操作直至经过矩阵中所有格子。根据经过顺序,在格子中依次填入1, 2, 3, ... , n2,便构成了一个螺旋矩阵。

下图是一个n = 4 时的螺旋矩阵。 

现给出矩阵大小n以及i和j,请你求出该矩阵中第i行第j列的数是多少。

 

【输入】

输入文件名为matrix.in。

输入共一行,包含三个整数n,i,j,每两个整数之间用一个空格隔开,分别表示矩阵大小、待求的数所在的行号和列号。

 

【输出】

输出文件名为matrix.out。

输出共一行,包含一个整数,表示相应矩阵中第i行第j列的数。

 

【输入输出样例】

matrix.in

matrix.out

4 2 3

14

 

【数据说明】

对于50%的数据,1 ≤ n ≤ 100;

对于100%的数据,1 ≤ n ≤ 30,000,1 ≤ i ≤ n,1 ≤ j ≤ n

首先看到这个题目 能想到的是数字由内而外的螺旋矩阵,就可以从内圈开始逐步模拟推出各个方框的数字,最后得出结果。

这样就可以得到规律:以左上角为坐标原点,向下为y轴正半轴,向右为x轴正半轴。

当n为偶数时,起点在(n/2+1,(n+1)/2)处。

当n为奇数时,起点在((n+1)/2, (n+1)/2)处。

那么就令int x,y为相应的数作为起点坐标,旋转规律如下:

数字递减的方向由 右 上 左 下的顺序进行旋转,每次改变方向,该点便沿此方向平移k次,然后再旋转,平移k(k=1)次,然后旋转,此时平移k+1次,以此类推,方向每改变两次,k=k+1。

运用int dir来储存方向 dir/4=1,2,3,4为每次平移的方向。

建立循环 for(int p=n;p>=1;p--)

将矩阵枚举出来后,就可以输出相应点的值了。

但是本题n<=30000 那么数组就要开9*10^8,既浪费空间也浪费时间,而且无法开出,所以这种方法在本题只适用前50%的数据。 那么怎么在不开数组、尽量不计算无关点的值就得出目标值呢? 通过观察,发现矩阵是由n/2层构成,每层格数相差2格,对顶角上的点的值变化也有规律,如果我们找到了目标点所在的层数,就能通过较少的平移求出答案,而不是浪费资源。 至于层数的寻找,在i,j∈n/2时是容易的, i,j中的最小值即为层数,层数ceng=i>j?j:i。

如果目标在其他位置,可通过对称的方式用相同的方法求出层数。

当i>n/2 i’=1+(n-i) j同理。

接下来可求到此层左上角的点的值:

int p=1

for(int m=1;m<=ceng;m++) P+=4*(n-1); 运用刚才的平移法则,可求到相应的点。 再优化: 当j>x且i=y时p(目标)=p+(j-x) ,平移判断

当i>y且j=x时p(目标)=p+(i-y) ,平移 判断

当x>j且i=y时p(目标)=p+(x-j) ,平移 判断

当y>i且j=x时p(目标)=p+(y-i) 判断

这样就可以AC了

~~~#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>

int main()
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
int n,i,j;
scanf("%d %d %d",&n,&i,&j);
int x=j,y=i;
int a=n/2;

<pre><code>if(n%2==0)//判断该数属于第几行
{
if(x>a)
x=1+(n-x);
if(y>a)
y=1+(n-y);
}
else
{
if(x>a+1)
x=1+(n-x);
if(y>a+1)
y=1+(n-y);
}

int ceng=x<y?x:y;
x=1;y=1;
int p=1;
for(int m=1;m<ceng;m++)
{
p+=4*(n-1);
n-=2;
x++;
y++;
}

if(y==i)
{
p+=j-x;
printf("%d",p);
return 0;
}
p+=n-1;
x+=n-1;
if(x==j)
{
p+=i-y;
printf("%d",p);
return 0;
}
p+=n-1;
y+=n-1;
if(y==i)
{
p+=x-j;
printf("%d",p);
return 0;
}
p+=n-1;
x-=n-1;
if(x==j)
{
p+=y-i;
printf("%d",p);
return 0;
}

return 0;
</code></pre>

}~~~


CTFer|NOIPer|CSGO|摸鱼|菜鸡