Модуль: Жадные алгоритмы


Задача

5 /9


Мелоне тестирует робота

Задача

Мелоне хочет протестировать свою новую разработку - робота, который способен перемещаться по лабиринтам.
Робот находится в прямоугольном лабиринте размера n × m. Каждая из клеток лабиринта либо пустая, либо занята препятствием. 
Робот может передвигаться между соседними по стороне клетками влево (символ «L»), вправо (символ «R»), вверх (символ «U») или вниз (символ «D»). Робот может переместиться в клетку, только если она пустая. Изначально робот находится в пустой клетке.

Мелоне хочет, чтобы робот прошелся по лексикографически минимальному циклу длины ровно k, который начинается и заканчивается в той клетке, в которой робот находится изначально. Роботу разрешается посещать любую клетку сколько угодно раз (включая стартовую).

Путь робота задаётся строкой, состоящей из символов «L», «R», «U» и «D». Например, если робот сначала пойдёт вниз, потом влево, затем вправо и вверх, то его путь записывается как «DLRU».

Помогите Мелоне определить какой именно путь робота соответствует лексикографически минимальному циклу длины ровно k или скажите, что такого не существует.

Входные данные:
В первой строке следуют три целых числа n, m и k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 106) — размеры лабиринта и длина цикла.
В каждой из следующих n строк следуют по m символов — описание лабиринта. Если символ равен «.», то текущая клетка пустая. Если символ равен «*», то текущая клетка занята препятствием. Если символ равен «X», то изначально робот находится в этой клетке, и она пустая. Гарантируется, что символ «X» встречается в лабиринте ровно один раз.

Выходные данные:
Выведите лексикографически минимальный путь Робота длины ровно k, который начинается и заканчивается в той клетке, в которой Робот находится изначально. Если такого пути не существует, выведите «IMPOSSIBLE» (без кавычек).

Примеры:
 
Входные данные Выходные данные
2 3 2
.**
X..
RL
5 6 14
..***.
*...X.
..*...
..*.**
....*.
DLDDLLLRRRUURU
3 3 4
***
*X*
***
IMPOSSIBLE



time 5000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Комментарий учителя