Виведи хом’ячків

Одного разу в будиночок вченого постукали декілька хом’ячків. Всі вони тихенько хлюпали носиками і витирали заплакані оченята. “Що сталось?” — запитав вчений, і почув у відповідь страшне повідомлення: два хом’ячки заблукали у вентиляційній системі, яку створили для охолодження суперкрутого комп’ютера. Вчений вирішив допомогти хом’ячкам врятувати своїх товаришів. Проблема в тому, що єдиний спосіб допомогти звірятам — це передати їм по радіо команди. Допоможіть вченому написати програму порятунку хом’ячків.

Лабіринт вентиляції — це плоска прямокутна пластина з вирізами. У лабіринті точно один вихід. Хом’ячки не відзначаються розумом і кмітливістю, самі вибратися з лабіринту не можуть. Проте вони можуть виконувати набір команд. Команди подаються обом хом’ячкам одночасно, і рухаються вони з однаковою швидкістю. Команди бувають такими:

• Вправо — R

• Вліво — L

• Вгору — U

• Вниз — D

Для простоти вважатимемо, що лабіринт складається з клітин. Кожна клітина може бути проходом, стіною або виходом. Хом’ячки можуть перебувати на одній клітині одночасно. Через стіну хом’ячки пройти не можуть. Більше того, вони настільки розгублені після блукання, що можуть вийти з лабіринту лише разом. Якщо тільки один з хом’ячків дістанеться вихідної клітини, він не залишає лабіринт і продовжує виконувати команди.