(matrix.cpp)
【问题描述】
一个n行n列的螺旋矩阵可由如下方法生成：
从矩阵的左上角（第1行第1列）出发，初始时向右移动；如果前方是未曾经过的格子， 则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入1, 2, 3, … , n2，便构成了一个螺旋矩阵。
现给出矩阵大小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
#include
#include
#include
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; 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
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/224418.html原文链接：https://javaforall.net
