求螺旋矩阵任意位置元素 洛谷P2239

之前在矩阵的模拟中，发过几篇输出螺旋矩阵的题目：输出螺旋矩阵，这几天又遇到了螺旋矩阵的新题目，不让你输出螺旋矩阵，而是给你一个下标(x,y)，输出当前 矩阵元素 的值。

题目描述

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

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

输入

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

输出

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

这题看到之后最朴素的思路就是，将螺旋矩阵打印，然后直接用O(1)的复杂度求出 (x,y)的值。结果TLE，因为我们看到n的范围30000，输出一个螺旋矩阵，需要内存n^2,时间n^2，所以无论从内存上还是时间上，这都不是一个好的办法，所以我们需要换一种思路。

所有人都会的思路，找规律-----我们根据题目可以知道这个元素的值百分百与x,y有关，不然他不可能给你(根据做题经验)。

那么，真的有规律吗？我们以一个矩阵来看，一般来说这种题奇数难判断，因为奇数多出一个数，所以我们以奇数为例。

(也许题目给你这个4*4就是为了让你找错规律，可恶的出题人）

下面附一个5*5的矩阵：

不同层颜色进行了区分，现在我们找一下规律：

x为所求元素，(i ,  j)  分别为x,y坐标：

1.第一行 : 我们发现纵坐标就是所求元素的值，即【if(i==1)  x=j;】

2.第二行 :我们发现找不到与横纵坐标有关的通式，并且在第n行之前x,y坐标没有一个通式表示，因为前面17 18 19 6没有通式。

3.第n行：他是一个递减的通式。我们把他与列连起来，就是3*n-1-j。

4.同样的，第一列通式：4*n-2-i，第n列通式：n+i-1。

5.这个时候注意，假设我们要求的这个元素是(1,5)，那么它既满足i==1，又满足j==n，这两个用哪个通式都可以求解，并且结果都是一样的，但是！细心一点会发现 如果输入(1,1)，既满足i==1，j==1。但他却不满足j==1时的通式。所以我们将j==1放到最后一个判断,如下图所示代码：

这样就能避免错误，为什么呢？经过上面三个判断，如果拿上图来说就只有元素 14 15 16没有被判断，而这三个绝对都符合j==1的通式。

6.好了规律也找到了，但是现在我们只能确定满足四种坐标的值，如果(2,3)怎么办：

继续看这个图，我们发现第二层(黄色)，其实就是由16推出来的，并且第二层所有的数，满足另一个螺旋矩阵，比如17=16+1,18=16+2。

其实就是这么一个图(为了方便我手写)

1    2   3     4     5

16  1   2     3    6

15  8   1    4    7

14  7    6    5   8

13 12  11  10  9

我们发现，如果要求第二层的某个数，只需要将他的上一层(第一层)的(2,1)位置的这个数加上。因为我们只知道最外层的规律，就需要将第二层成为最外层然后就可以直接算出某一个的值，然后加上上一层(2,1)这个位置的数，如果要把第二层当做最外层只需要n-2，可以举例试试。实在不懂看一下我手写的这个表，第二层成了一个从1开始的n=3的螺旋矩阵外层。

所以我们就可以根据这个思想，进行递归了。

第一步：首先判断这是不是最外层的点。

第二步：如果不是现在最外层的点，让他成为最外层(N-2,i-1,j-1)坐标要对应减一，因为上面一行没了，左边一行也没了。

第三步：如果是最外层的点，我们就retun对于这一层是最外层的值。然后在一次次由外往里面刨的过程中，每一个过程都保留(2,1)位置的值加上，这个地方如果递归不太懂，可能有点难理解。

PS：还有(2,1)这个位置的值是什么呢？就是4*(n-1)，假设最外层每条边都有n-1个值。

具体看代码叭：

 这样基本这道题就完成了，祝大家一次AC。

在仔细想想，其实做这种题，心里清楚如果暴力绝对会超时，而且内存会炸，那么我们只能找规律，根据题目的x，y找规律。好叭，其实身边朋友很多做出来没有用递归。那也怪我思维太弱了。就这样叭，继续加油！

update 2019.9.3更新高效算法: