3. Шарик в лабиринте
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (2)
Шарик бросается в дырку в
верхней крышке коробки, представляющей из себя
лабиринт. Коробку можно наклонять в 4 направлениях N, W, S и E
(как показано на рисунке, буква указывает опускаемую сторону прямоугольной
коробки) и управлять таким образом движением шарика. В нижней крышке
коробки есть другая дырка, через которую шарик вывалится, если он до
нее докатится. Крышки и стенки коробки непрозрачны, поэтому точное
местоположение шарика в коробке неизвестно. По этой причине изменять
направление движения шарика можно только, когда он докатится до какой-нибудь
стенки (препятствия) и остановится. Путем просвечивания коробки рентгеном
было выяснено расположение стенок в лабиринте.
Напишите программу, которая определит последовательность наклонов коробки,
позволяющую выкатить шарик из лабиринта.
Во входном файле в первой строке содержатся два целых числа `N` и `M`,
разделенных пробелом – размеры коробки (`2\ ≤\ N\ ≤\ 100`, `2\ ≤\ M\ ≤\ 100`).
Во следующих `N` строках содержится по `M` символов.
Символ '#' используется для обозначения стенки (препятствия).
Символ '.' (точка) обозначает свободное место.
Символ '@' обозначает вход, а символ '$' – выход.
Внешние стенки коробки во входном файле не описываются.
В выходной файл вывести последовательность, позволяющую выкатить
шарик из лабиринта, обозначая наклоны символами N, S, W, E
(соответствие показано на рисунке). Если
существует несколько вариантов вывести любой (один) из них.
Если вывести шарик из лабиринта невозможно, то программа
должна напечатать слово IMPOSSIBLE.
Пример ввода
4 4
@#.$
....
.#..
...#