loj#P6941. 「ICPC World Finals 2022」玩具火车轨道
「ICPC World Finals 2022」玩具火车轨道
题目描述
每个小孩和很多成年人都对玩具火车着迷。从蹒跚学步的孩子玩的玩具火车到业余爱好者精心制作的能摆满整个地下室的铁路模型,玩具火车都是一项利润丰厚的生意。玩具火车轨道建设公司(The Toy Train Tracks Construction Company, TTTCC)生产的火车轨道适合各个年龄段和技能水平。为了让老客户保持消费,并可能能吸引一些新客户,TTTCC 最近开始发布如何将火车轨道连接得更精致的指南。通常情况下,设计者会先想出一个有趣的轨道布局,然后公布布局以及拼成这种布局所需的不同轨道段(例如曲线和直线部分)的数量。但 TTTCC 最近了解到,许多客户正在寻找相反的情况:他们已经有了火车轨道段(也许是在奶奶的阁楼上找到的),并希望用它们来创建一个大型火车线路。这有多难呢?
为了研究布局创建过程自动化的可行性,TTTCC 希望使用两种不同的轨道段构建轨道:直轨道段和 度弯轨道段(见图 U.1)。
将这些轨道段放置在正方形网格上,每个轨道段正好占据一个网格单元,即可形成合法的布局。两种轨道都可以以 度为单位旋转。一条「合适」的轨道需要是连通的,并形成一个闭合的环路。给定一组直轨道段和弯轨道段,可以形成的最长闭合环路是什么?
输入格式
一行两个整数 和 ,分别表示可用的直轨道段数和弯轨道段数()。
输出格式
在最多使用 个直轨道段和 个弯轨道段的情况下,输出一个长度(以使用的轨道段数表示)最长的轨道环路。该环路必须是封闭的,且不能与自身相交。如果存在多个长度最长的环路,输出任意一个均可。
如果环路的长度为 ,则输出一个长度为 的字符串,其中的字符代表在一次遍历中遇到的环路上的轨道段。字符 S
代表直轨道段,L
代表左转的弯轨道段,R
代表右转的弯轨道段。
4 12
LSRLLRLSLSRLLSRL
1 5
LLLL