Подразделы

Другие разделы

Дата и время

20/04/2024 04:23:32

Авторизация

Зарегистрироваться
Восстановить пароль

Областная олимпиада школьников по информатике (командные соревнования)

1. Гирлянда 2. Подарки 3. Fiat lux! 4. Канатная дорога 5. Шпионское сообщение 6. Лабиринт 7. Клубы 8. Хакер 9. Плоттер

6. Лабиринт

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

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

…

Через три минуты они опять были в центре.

После этого они просто-таки не могли оттуда уйти. В какую бы сторону они ни сворачивали, все пути приводили их в центр. Это стало повторяться с такой правильностью, что некоторые просто оставались на месте и ждали, пока остальные прогуляются и вернутся к ним. Гаррис опять извлек свой план, но вид этой бумаги привел толпу в ярость. Гаррису посоветовали пустить план на папильотки. Гаррис, по его словам, не мог не сознавать, что до некоторой степени утратил популярность.

Наконец все совершенно потеряли голову и во весь голос стали звать сторожа. Сторож пришел, взобрался на стремянку снаружи лабиринта и начал громко давать им указания.

Джером К. Джером "Трое в одной лодке, не считая собаки"

Сторож не видит заблудившихся в лабиринте людей, а забрался на стремянку, чтобы его было лучше слышно. Он может указывать группе направление движения – север, юг, запад или восток. Группа не выполняет инструкции, если мешает стена или препятствие. Напишите программу, которая для любого лабиринта определяет последовательность инструкций по выводу людей, находящихся в неизвестном месте лабиринта.

Во входном файле в первой строке содержится одно целое число – размер лабиринта в клетках `N` (`2\ ≤\ N\ ≤\ 10`). Далее следует `N` строк по `N` символов – план лабиринта. Лабиринт по периметру полностью окружен стеной, не показанной на плане. Символ '.' означает свободную клетку. Символ '#' – клетку, занятую препятствием. Символ '@', встречающийся на карте единственный раз, означает выход из лабиринта. Люди, попавшие на эту клетку, дальнейшие инструкции сторожа не выполняют. Из любой свободной клетки существует путь до клетки с выходом. Север на плане находится вверху, запад – слева.

В выходной файл вывести последовательность инструкций, при выполнении которой люди независимо от их начального положения обязательно окажутся на клетке с выходом. В строке могут встречаться только следующие инструкции: 'N' – пройти одну клетку на север, 'S' – на юг, 'W' – на запад, 'E' – на восток. Можно вывести любой из вариантов такой последовательности, не обязательно самый короткий.

Пример ввода

3
.@.
.#.
.#.

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

NNEW