求螺旋矩阵任意位置元素&&洛谷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放到最后一个判断,如下图所示代码：

    if(i==1) x=j;
    else if(j==n) x=n-1+i;
    else if(i==n) x=n*3-j-1;
    else if(j==1) x=4*n-i-2;

这样就能避免错误，为什么呢？经过上面三个判断，如果拿上图来说就只有元素 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个值。

具体看代码叭：

#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const ll INF=1e9;
/*坚持不懈，无懈可击*/
/*中国有句古话，叫做置之死地而后生！*/
int bg(int n, int i, int j)
{
    if(i==1) return j;
    if(j==n) return n-1+i;
    if(i==n) return n*3-j-1;
    if(j==1) return 4*n-i-2;//以上就是如果当前的点就是最外层，直接返回
    return 4*n-4+bg(n-2,i-1,j-1);//如果不是最外层，就让下一层的成为最外层，并且要加上【这一层】！！！！(2,1)位置上的值。
}
int main()
{
    int n,x,y;
    scanf("%d",&n);
    scanf("%d%d",&x,&y);
    printf("%d\n",bg(n,x,y));
    return 0;
}

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

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

update 2019.9.3更新高效算法:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll work(ll n,ll a,ll b)
{
	ll q=min(min(a,b),min(n-a+1,n-b+1));
	ll ans;
	if(a<=b)
	{
		q--;
		ans=4*(n-q)*q+a+b-2*(q+1)+1;
    }
    else 
		ans=4*(n-q)*q-a-b+2*q+1;
	return ans;
}
int main()
{
	ll a,b;
	while(~scanf("%lld%lld%lld",&n,&a,&b))
	{
		printf("%lld\n",work(n,a,b));
	}
}