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


上一篇:windows下使用火狐浏览器插件AutoProxy+MyEnTunnel+SSH访问海外站点(转)


下一篇:火狐浏览器+Firebug+FirePath测试Xpath