e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Bring hamsters (RU)

Bring hamsters (RU)

prb213 Однажды в домик Лосяша постучалось несколько хомячков. Все они тихонько хлюпали носиками и вытирали заплпканные глазки. "Что случилось?" - спросил Лосяш, и услышал в ответ ужасное сообщение: два хомячка заблудились в вентляционной системе, которую соорудил Пин для охлаждения своего суперкрутого компа. Лосяш решил помочь хомячкам спасти своих товарищей. Проблема в том, что единственный способ помочь зверькам - это передать им по радио команды. Помогите Лосяшу написать программу спасения хомячков.

Лабиринт вентиляции представляет собой плоскую прямоугольную пластину с прорезанными внутри полостями. В лабиринте имеется ровно один выход. Хомячки не отличаются умом и сообразительностью и сами выбраться из лабиринта не могут. Зато они могут выполнять набор команд. Команды подаются обоим хомячкам одновременно. Хомячки двигаются с одинаковой скоростью. Команды бывают следующих типов:

• Ползти вправо - R,

• Ползти влево - L,

• Ползти вперёд - U,

• Ползти назад - D.

Для простоты будем считать, что лабиринт состоит из клеток. Каждая клетка может быть либо проходом, либо стеной, либо выходом. Хомячки могут одновременно находиться на одной клетке. Через стену вентиляции хомячки ходить не могут. Более того, они так отупели от блуждания в лабиринте, что могут выйти из лабиринта только вдвоём. Если по клетке-выходу проходит только один хомячок, то он не выходит из лабиринта и продолжает выполнять команды.

Входные данные

В первой строке заданы два целых числа H и W - размеры лабиринта по вертикали и горизонтали соответственно. Далее следует H строк по W символов, каждый из которых может быть: * - выход, 1 - первый хомячок, находящийся в проходе, 2 - второй хомячок, находящийся в проходе, . - свободная дорожка, # - пропасть. H, W <= 100.

Выходные данные

В первой строке вывести длину программы. Во второй строке файла вывести программу для хомячков.

Time limit 5 seconds
Memory limit 64 MiB
Input example #1
4 5
.....
.....
...2.
..1*.
Output example #1
4
RRLD