【题意】
已知：n，r，c（n<=30000）
条件：给定n行n列的螺旋矩阵（从矩阵的左上角(1,1)出发，初始时向右移动；如果前方是未曾经过的格子， 则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入 1, 2, 3, ... , n^2）
/*
如下图是一个 n = 4 时的螺旋矩阵：
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
求：n阶螺旋矩阵第r行第c列的值
【构思】
最常见的方法就是直接构造，时间复杂度O（n^2），在本题会超时；
那么就要化简运算：发现每层有4个转弯点，可以按转弯点转移，若(r,c)在其中则直接输出答案。
这样每层就只有4个点，时间复杂度为O(n)
【实现】
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int cnt,n,x,y,rx,ry;
int main(void)
{
freopen("test.in","r",stdin);
scanf("%d%d%d",&n,&rx,&ry);
for (int i=n-1;;i-=2)
{
x++,y++;
if (x==rx&&y<=ry&&ry<=y+n-1)
{
printf("%d\n",cnt+ry-y+1);
break;
}
cnt+=i;
y+=i;
if (y==ry&&x<=rx&&rx<=x+n-1)
{
printf("%d\n",cnt+rx-x+1);
break;
}
cnt+=i;
x+=i;
if (x==rx&&ry<=y&&y-n+1<=ry)
{
printf("%d\n",cnt+y-ry+1);
break;
}
cnt+=i;
y-=i;
if (y==ry&&rx<=x&&x-n+1<=rx)
{
printf("%d\n",cnt+x-rx+1);
break;
}
cnt+=i;
x-=i;
}
return 0;
}
【回顾】
1、构造类问题的解决方法 ①模拟 ②按照特殊点转移
2、构造类问题关键在于找出层次和特殊点