#P4148. [AMPPZ2014]Pillars

    ID: 3364 传统题 5000ms 256MiB 尝试: 137 已通过: 49 难度: 8 上传者: 标签>难度分类提高+/省选-构造与建模图构造局部修复模拟与实现技巧直接模拟CF2400鸣谢Claris上传

[AMPPZ2014]Pillars

[AMPPZ 2014] Pillars

题目描述

一个长为 nn、宽为 mm 的矩形仓库被划分成单位方格。其中有 ff 根立柱,每根占据一个 2×22\times2 的方格块。两根立柱中心之间的欧几里得距离至少为 66,每根立柱的中心到仓库各外墙的距离均至少为 33。

要铺设一根闭合的供暖管道,使它经过所有未被立柱占据的单位方格中心各一次。管道线段必须平行于坐标轴,只能在方格中心转弯。管道从左下角方格的中心出发,最后回到该处。

以仓库的左下角为坐标原点,横坐标范围为 [0,n][0,n],纵坐标范围为 [0,m][0,m]。因此单位方格中心的两个坐标都是半整数,管道起点为 (12,12)(\tfrac12,\tfrac12)。

输入格式

第一行三个整数 n,m,fn,m,f(1≤n,m≤1 0001\le n,m\le1\,000,n,mn,m 都是偶数),分别表示仓库尺寸与立柱数。

接下来 ff 行,每行两个整数 xi,yix_i,y_i(0≤xi≤n0\le x_i\le n,0≤yi≤m0\le y_i\le m),表示一根立柱的中心。

输出格式

如果无法铺设管道,输出 NIE。否则第一行输出 TAK,第二行输出一个长为 nm−4fnm-4f 的字符串,依次描述从起点出发的每一步。任意一个合法方案均可。

字符 方向 位移
G 上 (0,1)(0,1)
D 下 (0,−1)(0,-1)
P 右 (1,0)(1,0)
L 左 (−1,0)(-1,0)

样例 #1

样例输入 #1

12 6 2
3 3
9 3

样例输出 #1

TAK
PPPPPPPPPPPGGGLDDLLLLLGPPGLLLDDLLLGGGPPPPPPPPPPGLLLLLLLLLLLDDDDD

样例说明

灰色区域是立柱,黑线是样例输出给出的管道。

两根立柱与样例供暖管道