#P4148. [AMPPZ2014]Pillars
[AMPPZ2014]Pillars
[AMPPZ 2014] Pillars
题目描述
一个长为 、宽为 的矩形仓库被划分成单位方格。其中有 根立柱,每根占据一个 的方格块。两根立柱中心之间的欧几里得距离至少为 ,每根立柱的中心到仓库各外墙的距离均至少为 。
要铺设一根闭合的供暖管道,使它经过所有未被立柱占据的单位方格中心各一次。管道线段必须平行于坐标轴,只能在方格中心转弯。管道从左下角方格的中心出发,最后回到该处。
以仓库的左下角为坐标原点,横坐标范围为 ,纵坐标范围为 。因此单位方格中心的两个坐标都是半整数,管道起点为 。
输入格式
第一行三个整数 (, 都是偶数),分别表示仓库尺寸与立柱数。
接下来 行,每行两个整数 (,),表示一根立柱的中心。
输出格式
如果无法铺设管道,输出 NIE。否则第一行输出 TAK,第二行输出一个长为 的字符串,依次描述从起点出发的每一步。任意一个合法方案均可。
| 字符 | 方向 | 位移 |
|---|---|---|
G |
上 | |
D |
下 | |
P |
右 | |
L |
左 |
样例 #1
样例输入 #1
12 6 2
3 3
9 3
样例输出 #1
TAK
PPPPPPPPPPPGGGLDDLLLLLGPPGLLLDDLLLGGGPPPPPPPPPPGLLLLLLLLLLLDDDDD
样例说明
灰色区域是立柱,黑线是样例输出给出的管道。
