|
Стрелки - 2
(Время: 1 сек. Память: 16 Мб Сложность: 68%)
Костя нашел головоломку, в которую его дедушка играл в детстве - доску n_m клеток, на некоторых из которых прикреплены вращающиеся стрелки (Костя предполагает, что раньше стрелки были на всех клетках). К сожалению, дедушка уже не помнит, что нужно было сделать в этой головоломке, поэтому Костя придумывает правила сам.
Он заметил следующую особенность. Направим каждую стрелку на одну из соседних клеток, на которой тоже есть стрелка (оказалось, что одиноко стоящих стрелок на доске нет). Теперь на доске появились циклы, идя по которым, мы всегда будем идти по направлению стрелок. Например, при расстановке, которая отражена на рисунке, есть четыре цикла.
Костя придумал сразу два задания: «поставить стрелки так, чтобы число циклов было минимально», и «поставить стрелки так, чтобы число циклов было максимально». Пока Костя ищет решение вручную, напишите программу, находящую требуемые расстановки.
Входные данные
Входной файл INPUT.TXT содержит Первая строка входного файла содержит числа n и m (1 ≤ n, m ≤ 100). Следующие n строк по m символов содержат описание доски: символ «?» соответствует клетке со стрелкой, а символ «.» - пустой клетке.
Выходные данные
В выходной файл OUTPUT.TXT выведите сначала расстановку, в которой число циклов минимально, а затем расстановку, в которой число циклов максимально. Разделите расстановки одной пустой строкой.
Расстановку стрелок выводите, заменив в описании доски символы «?» на символы, соответствующие направлениям стрелок. Используйте символы «R», «L», «U» и «D» для обозначения направлений вправо, влево, вверх и вниз соответственно.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 |
3 4
????
????
.??. |
RRRD
UUDL
.UL.
RLDD
RLUU
.RL. |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
