UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4148. [AMPPZ2014]Pillars

Statistics 下载数据

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

鸣谢Claris上传