8148: BZOJ4148：[AMPPZ2014]Pillars
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
给定一个n*m的矩形，其中有f个2*2的障碍物，其中任意两个障碍物中心之间的欧几里得距离至少为6， 且每个障碍物的中心到边缘的距离至少为3。请找到一条从左下角(1,1)出发经过所有没有障碍物的点各 一次的且最后回到左下角的回路。
输入格式
第一行包含三个整数n,m,f(1<=n,m<=1000且n,m都为偶数)。 接下来f行，每行两个整数x,y(1<=x<n,1<=y<m)，表示该障碍物左下角的坐标。
输出格式
如果无解，输出NIE，否则第一行输出TAK，第二行输出方案。 方案包含n*m-4*f个字符，第i个字符表示第i步的移动方向，用G表示上，D表示下，L表示左，P表示右。
样例输入
12 6 2 3 3 9 3
样例输出
TAK PPPPPPPPPPPGGGLDDLLLLLGPPGLLLDDLLLGGGPPPPPPPPPPGLLLLLLLLLLLDDDDD
提示
题目来源
鸣谢Claris上传