NOIP 2014 普及组 T3 螺旋矩阵

【题意】

已知：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、构造类问题关键在于找出层次和特殊点

巴特西

NOIP 2014 普及组 T3 螺旋矩阵

最新文章

热门文章