RollerCoasters
Национална Олимпиада по Информатика 2017, Контрола 1
Time Limit: 0.2s, Memory Limit: 128MiB
Увеселителният парк ShopiaLand в града, в който живее Ели, е затворен от вече над десет години. Момичето е твърдо решено да върне радостта на децата – възможността да се качат на виенско колело, да покарат блъскащи се колички, или да се пуснат с влакче на ужасите. За целта тя е убедила инвеститор да даде пари за нов увеселителен парк. На Ели се пада честта да проектира маршрутите на влакчетата.

Можем да представим мястото, където ще са влакчетата, като правоъгълник с N реда и M колони. Всяка "клетка" е или празна, или съдържа пилон, който поддържа сегмент от релсите.

Има два основни вида сегменти релси: "прав участък" и "завой на 90 градуса". Правият участък може да бъде поставян както хоризонтално, така и вертикално. Поради специфичността на пилоните, обаче, всеки от завоите трябва задължително да гледа в дадена посока (като завива в една от двете съседни).
  • Сегмент с прав участък (който във входа ще представяме с буквата 'S') може да бъде поставен вертикално '║' (ASCII код 186) или хоризонално '═' (ASCII код 205).
  • Сегмент със завой наляво (който във входа ще представяме с буквата 'L') може да бъде поставен надолу '╗' (ASCII код 187) или нагоре '╝' (ASCII код 188).
  • Сегмент със завой нагоре (който във входа ще представяме с буквата 'U') може да бъде поставен наляво '╝' (ASCII код 188) или надясно '╚' (ASCII код 200).
  • Сегмент със завой надясно (който във входа ще представяме с буквата 'R') може да бъде поставен нагоре '╚' (ASCII код 200) или надолу '╔' (ASCII код 201).
  • Сегмент със завой надолу (който във входа ще представяме с буквата 'D') може да бъде поставен надясно '╔' (ASCII код 201) или наляво '╗' (ASCII код 187).

Може да има няколко независими пътя на влакчета (примерно "за деца", "за възрастни", и "за любители на силните усещания"). Инвеститорът държи върху всеки пилон да има поставена релса и всички релси да участват в пътя на някое влакче. Разбира се, всеки път на влакче трябва да образува цикъл (тоест, движейки се по него да се върнем там, откъдето сме тръгнали). Празните клетки трябва да си останат празни.

Сега Ели има пред себе си план на мястото, където ще бъдат влакчетата. За всяка клетка, която съдържа пилон, е дадено дали държи прав участък или завой (и, съответно, с каква "насоченост" е завоят). Вие решавате да помогнете на Ели да "насочи" релсите, така че да са изпълнени всички изисквания.
Вход
На първия ред на стандартния вход ще бъдат зададени две цели числа N и M – съответно броя редове и колони на площадката с влакчетата. На всеки от следващите N реда ще е зададен стринг с M символа от азбуката {'.', 'S', 'L', 'U', 'R', 'D'}. С '.' бележим празна клетка. С буквата 'S' бележим прав участък. С буквите 'L', 'U', 'R', и 'D' отбелязваме, съответно, завой, едната част от който гледа задължително на ляво, горе, дясно, и долу.
Изход
На стандартния изход изпечатайте N реда, всеки съдържащ по M символа, описващи крайния план на влакчетата. Ако има повече от едно решение, изведете това, чието най-дълъг маршрут на влакче (последователност от клетки, които образуват цикъл) е възможно най-дълъг. Ако има повече от един такъв, изведете който и да е от тях. В случай, че няма нито едно възможно решение, вместо това на единствен ред изведете "IMPOSSIBLE".
Ограничения
  • 1 ≤ N, M ≤ 500
Примерен Вход Примерен Изход
8 6 DSSSSD SRSDDL SULSRL ULSSRU RLRUUD SDLDLS SRUSSS USSUUU ╔════╗ ║╔═╗╔╝ ║╚╗║╚╗ ╚╗║║╔╝ ╔╝╚╝╚╗ ║╔╗╔╗║ ║╚╝║║║ ╚══╝╚╝
2 3 DRL US. IMPOSSIBLE
8 29 DLRDRSSDDD..DDDSSLDSSDDLDSSSL SSSSSDDSSS..SSUSDSSRDSSSUSSLS SSSSSSSSSSRSUSDSUSSSSSSS...SS SULSSSSSSSSDLSSDSLSSSSSS...SS SDDSSSSSSULSSSSUSLSRUSSS...SS SSSSSSSSSRSLSSRSSUUSSURU...RL SSSSSULSSS..SSDSSSSSSSSSSSSSL RLUURSSLRL..RUUSSSSSSSSSSSSSL ╔╗╔╗╔══╗╔╗..╔╗╔══╗╔══╗╔╗╔═══╗ ║║║║║╔╗║║║..║║╚═╗║║╔╗║║║╚══╗║ ║║║║║║║║║║╔═╝║╔═╝║║║║║║║...║║ ║╚╝║║║║║║║║╔╗║║╔═╝║║║║║║...║║ ║╔╗║║║║║║╚╝║║║║╚═╗║╚╝║║║...║║ ║║║║║║║║║╔═╝║║╚══╝╚══╝╚╝...╚╝ ║║║║║╚╝║║║..║║╔═════════════╗ ╚╝╚╝╚══╝╚╝..╚╝╚═════════════╝
В първия пример няма празни клетки - във всяка от тях има пилон. Във втория пример няма как релсите да образуват затворен цикъл. В третия пример е показано едно възможно нареждане на дъската. Забележете, че празните клетки също трябва да бъдат изпечатани.
Забележка
За правилна визуализация на изхода, ползвайте ASCII кодова таблица CP866. Кодовата таблица обаче няма значение за тестването на решението ви, стига да изпечатвате байтове (char-ове) с дадените в условието стойности.
Мрън!