<ПРЕД Задача:
СЛЕД>
Задачу решили 53 пользователя: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Побег

Time limit = 2 секунд(ы)

Преступник Николай Борзов сбежал из тюрьмы и за ним ведется охота. Он находится в густом прямоугольным лесу, в котором вдоль и поперек через одинаковое расстояние в один километр идут просеки. Николай может двигаться только по просекам и в данный момент он находится на пересечении просек (точка A).

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

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

Поздравляем, это — вы.

Но на этот раз вам ничего не заплатят, а просто сохранят жизнь.

Напишите для мафии программу, которая по данной карте проводов строит кратчайший путь из точки A в точку B. Путь должен идти по просекам и не пересекать ни один из проводов.

Вход

Выбраны следующие координаты: ось X идёт с запада на восток, а ось Y — с юга на север. Лес представляет собой прямоугольник [0, N] × [0, M], 2 < N ≤ 100, 2 < M \le 100. По крайним просекам преступник также может перемещаться.

Первые две строки входа имеют следующий формат:

N M K
x1 y1 x2 y2

Здесь (x1, y1) и (x2, y2) — координаты точек A и B соотвественно.

Далее в K ( K < 11000 ) строчках перечислены координаты концов проводов --- в каждой строке по четыре числа, разделенных пробелами. Все координаты --- целые числа из отрезков [0, N] и [0, M].

Выход

Описание пути либо ``NO SOLUTION'', если решения нет. Путь описывается двумя строками. В первой строке дана его длина (в километрах), а вторая содержит последовательность букв ``N'', ``S'', ``E'', ``W'' (север, юг, восток и запад соответственно) записанными в одну строку без пробелов.

Вход#1
4 5 3
3 1 3 4
2 2 4 3
0 4 1 4
2 4 2 5
Выход#1
7
WWNNEEN
Вход#2
4 5 3
3 1 3 4
2 2 4 3
0 4 1 4
2 2 2 3
Выход#2
NO SOLUTION

Автор:
Андрей Уланов, личная олимпиада МФТИ, 7 октября 2007
4 декабря 2007

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 170ms

SW soft NIX
ID = 3.219.167.194