10
16
2015
1

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: 662
Avatar_small
AP 1st Inter Botany 说:
2022年9月08日 20:08

In intermediate education, Botany is a very important subject for science group students for part-1 and part-2 first and the second year of junior and senior intermediate students, and the BIEAP has conducted the General Science examination tests including botany subject, download AP inter Botany Model Paper 2023 AP 1st Inter Botany Question Paper Pdf with solutions for all 1st and 2nd-year students for paper-1 and paper-2 exams 2023.


登录 *


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