【AMPPZ2014】【BZOJ4148】Pillars

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上传

夏令营卢爷讲过 还是不会做
然而现在只记得他说”乌拉乌拉乌拉”大概当时也只听到了乌拉乌拉乌拉
所以最后翻了WC2015的课件和Claris题解重学了构造
Clar

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！