3263933_ac_500ms_8164k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

int N;
int visited[1001][1001];
int matrix[1001][1001];
int array[4000][2];

int main()
{
	int mov[][2] = {{-1,0},{0,1},{1,0},{0,-1}};
	int nextdir[] = {1,2,3,0};
	int i, j, cas = 1;

	while(scanf("%d",&N)==1,N){
	for(i = 0; i < N; i++)
	{
		for(j = 0; j < N; j++)
		{
			scanf("%d",&matrix[i][j]);
			visited[i][j] = 0;
		}
	}
	int dir, cnt, index, value, pos, error;
	dir = 1;
	i = 0;j = 0;
	error = 0;
	for(int k = 0; !error && k < (N+1)/2; k++)
	{
		cnt = index = 0;
		value = i*N+j+1;
		pos = -1;
		if(k==(N+1)/2-1&&N%2==1)
		{
			error = value!=matrix[i][j];
			break;
		}
		while(cnt < 4)
		{
			visited[i][j] = 1;
			array[index][0] = matrix[i][j];
			array[index++][1] = i*N+j+1;
			if(matrix[i][j]==value)
			{
				pos = index-1;
			}
			int ii, jj;
			ii = i+mov[dir][0];
			jj = j+mov[dir][1];
			if(ii >= N || jj >= N || ii < 0 || jj < 0 || visited[ii][jj] == 1)
			{
				cnt++;
				dir = nextdir[dir];
			}
			i += mov[dir][0];
			j += mov[dir][1];
		}
		if(k==(N+1)/2-1)
		{
			index--;
		}
		if(pos==-1)
		{
			error = 1;
			break;
		}
		int l;
		for(l = pos, cnt = 0; cnt < index; l++,cnt++)
		{
			if(array[l%index][0]!=array[cnt][1])
			{
				error = 1;
				break;
			}
		}
	}
	printf("%d. ",cas++);
	puts(error?"NO":"YES");
	}
	return 0;
}