images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 21:24:52

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

142. Лабиринт

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Попав внутрь лабиринта, они вскоре встретили людей, которые сказали, что находятся здесь три четверти часа и что с них, кажется, хватит. Гаррис предложил им, если угодно, последовать за ним. Он только вошел, сейчас повернет направо и выйдет. Все были ему очень признательны и пошли за ним следом. По дороге они подобрали еще многих, которые мечтали выбраться на волю, и, наконец, поглотили всех, кто был в лабиринте. Люди, отказавшиеся от всякой надежды снова увидеть родной дом и друзей, при виде Гарриса и его компании воспряли духом и присоединились к процессии, осыпая его благословениями.
…
Через три минуты они опять были в центре.
После этого они просто-таки не могли оттуда уйти. В какую бы сторону они ни сворачивали, все пути приводили их в центр. Это стало повторяться с такой правильностью, что некоторые просто оставались на месте и ждали, пока остальные прогуляются и вернутся к ним. Гаррис опять извлек свой план, но вид этой бумаги привел толпу в ярость. Гаррису посоветовали пустить план на папильотки. Гаррис, по его словам, не мог не сознавать, что до некоторой степени утратил популярность.
Наконец все совершенно потеряли голову и во весь голос стали звать сторожа. Сторож пришел, взобрался на стремянку снаружи лабиринта и начал громко давать им указания.
Джером К. Джером "Трое в одной лодке, не считая собаки"
Сторож не видит заблудившихся в лабиринте людей, а забрался на стремянку, чтобы его было лучше слышно. Он может указывать группе направление движения – север, юг, запад или восток. Группа не выполняет инструкции, если мешает стена или препятствие. Напишите программу, которая для любого лабиринта определяет последовательность инструкций по выводу людей, находящихся в неизвестном месте лабиринта.
Во входном файле в первой строке содержится одно целое число – размер лабиринта в клетках `N` (`2\ ≤\ N\ ≤\ 10`). Далее следует `N` строк по `N` символов – план лабиринта. Лабиринт по периметру полностью окружен стеной, не показанной на плане. Символ '.' означает свободную клетку. Символ '#' – клетку, занятую препятствием. Символ '@', встречающийся на карте единственный раз, означает выход из лабиринта. Люди, попавшие на эту клетку, дальнейшие инструкции сторожа не выполняют. Из любой свободной клетки существует путь до клетки с выходом. Север на плане находится вверху, запад – слева.
В выходной файл вывести последовательность инструкций, при выполнении которой люди независимо от их начального положения обязательно окажутся на клетке с выходом. В строке могут встречаться только следующие инструкции: 'N' – пройти одну клетку на север, 'S' – на юг, 'W' – на запад, 'E' – на восток. Можно вывести любой из вариантов такой последовательности, не обязательно самый короткий.

Пример ввода

3
.@.
.#.
.#.

Вывод для примера

NNEW
loading