10
16
2015
0

4148: [AMPPZ2014]Pillars

4148: [AMPPZ2014]Pillars

Time Limit: 5 Sec  Memory Limit: 256 MBSec  Special Judge
Submit: 62  Solved: 33
[Submit][Status][Discuss]

Description

给定一个n*m的矩形,其中有f个2*2的障碍物,其中任意两个障碍物中心之间的欧几里得距离至少为6,
且每个障碍物的中心到边缘的距离至少为3。请找到一条从左下角(1,1)出发经过所有没有障碍物的点各
一次的且最后回到左下角的回路。

 

Input

第一行包含三个整数n,m,f(1<=n,m<=1000且n,m都为偶数)。
接下来f行,每行两个整数x,y(1<=x<n,1<=y<m),表示该障碍物左下角的坐标。

 

Output

如果无解,输出NIE,否则第一行输出TAK,第二行输出方案。
方案包含n*m-4*f个字符,第i个字符表示第i步的移动方向,用G表示上,D表示下,L表示左,P表示右。

 

Sample Input

12 6 2
3 3
9 3

Sample Output

TAK
PPPPPPPPPPPGGGLDDLLLLLGPPGLLLDDLLLGGGPPPPPPPPPPGLLLLLLLLLLLDDDDD

HINT

 

 

Source

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char a[1010][1010];
int x,y,n,m,f;
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9'){if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
int main(){
	n = read();m = read();f = read();
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (i&1) a[i][j] = 'D';else a[i][j] = 'G';
	for (int i=1;i<=n;i++){
		if (i<n) a[i][1] = 'P';
		if (i>1 && i&1) a[i][2] = 'L';
		if (!(i&1)) a[i][m] = 'L';
	}
	for (int i=1;i<=f;i++){
		x = read();y = read();
		if (x&1){
			a[x+1][y-1] = 'L';
			a[x][y+2] = 'P';
			a[x+1][y+2] = 'P';
			a[x+2][y+3] = 'L';
		}
		else if (y==3){
			a[x][1] = 'G';
			a[x][2] = 'P';
			a[x+1][2] = 'D';
			a[x+1][y+2] = 'L';
		}
		else {
			a[x+1][y+2] = 'L';
        	a[x][y-1] = 'P';
        	a[x+1][y-1] = 'P';
    		a[x+2][y-2] = 'L';
		}
	}
	printf("TAK\n");
	for (x = y = 1,n = n*m-4*f;n--;){
		printf("%c",a[x][y]);
		if (a[x][y]=='L') x--;
		else if (a[x][y]=='P') x++;
		else if (a[x][y]=='D') y--;
		else y++;
	}
}
Category: BZOJ题解 | Tags: | Read Count: 338

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com