Занятие 10

В небольшом городе, имеющем квадратную форму, дорожные службы создали сложную сеть дорог и берут большие штрафы за нарушение правил движения. Путешественник хочет пересечь этот город, не нарушая правил движения. Для этого он купил на бензоколонке карту города и ввел ее в бортовой компьютер. Путешественник въезжает в город с запада по шоссе в северо-западный угол города и должен выехать по шоссе, ведущему на восток, из юго-восточного угла. Напишите программу, которая поможет путешественнику найти кратчайший путь в городе-лабиринте.

Во входном файле в первой строке содержится число `n` (`2\ ≤\ n\ ≤\ 20`) – размеры города. Далее следует `n` строк по n символов в каждой строке – информация о перекрестках. В городе существует всего три вида перекрестков. На перекрестке первого типа, обозначаемого во входном файле символом '+' (плюс), запрещены любые повороты, и необходимо продолжать движение в том же направлении. На перекрестке второго типа, обозначаемого символом '|' (вертикальная черта), при движении с запада на восток или с востока на запад нужно обязательно повернуть на север или на юг, а при движении с севера на юг или с юга на север – продолжить движение в том же направлении. На перекрестке третьего типа, обозначаемого символом '-' (минус), при движении с юга на север или с севера на юг нужно обязательно повернуть на запад или на восток, а при движении с востока на запад или с запада на восток – продолжить движение в том же направлении.

В выходной файл вывести кратчайший путь от первого перекрестка до выезда из города. Для каждого перекрестка, который встретится на пути путешественника, нужно указать направление дальнейшего движения – N (север), S (юг), W (запад) или E (восток). Если проехать через город без нарушения правил невозможно, то вывести сообщение "IMPOSSIBLE".

3
-|+
|-|
-++

ESWSEEE