eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Цивилизация

Цивилизация

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Карта мира в компьютерной игре “Цивилизация” версии 1 представляет собой прямоугольник, разбитый на квадратики. Каждый квадратик может иметь один из нескольких возможных рельефов, для простоты ограничимся тремя видами рельефов - поле, лес и вода. Поселенец перемещается по карте, при этом на перемещение в клетку, занятую полем, необходима одна единица времени, на перемещение в лес - две единицы времени, а перемещаться в клетку с водой нельзя.

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

Входные данные

Во входном файле записаны два натуральных числа N и M, не превосходящих 1000 - размеры карты мира (N - число строк в карте, M - число столбцов). Затем заданы координаты начального положения поселенца x и y, где x- номер строки, y - номер столбца на карте (1xN, 1yM), строки нумеруются сверху вниз, столбцы - слева направо. Затем аналогично задаются координаты клетки, куда необходимо привести поселенца.

Далее идет описание карты мира в виде N строк, каждая из которых содержит M символов. Каждый символ может быть либо "." (точка), обозначающим поле, либо "W", обозначающим лес, либо "#", обозначающим воду. Гарантируется, что начальная и конечная клетки пути переселенца не являются водой.

Выходные данные

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

Если дойти из начальной клетки в конечную невозможно, выведите число -1.

Пример

Входные данные #1
4 8 1 1 4 8
....WWWW
.######.
.#..W...
...WWWW.
Выходные данные #1
13
SSSEENEEEEES