螺旋矩阵

(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>

}~~~