螺旋矩阵
(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>
}~~~