El Judge

Online MIPT programming contest | РУССКИЙ |

<PREV Problem: | NEXT> |

` < ` |
---|

Time limit = 2 second(s)

(*THIS* IS *DRAFT*)

Prisoner Nickolay Borsov escaped from prison and now he is in the forest. And forest is very dense. One can use only paths going through it.

Paths are equally distanced (1 kilometer) straight line going from the south to the north, and from the west to the east.

Forest is rectangular.

Police wants to catch him and make catching barriers, which are straight segment with endpoints ant paths intersections.

Nickolay should find the way from point *A* to point *B* (where his frinds are waining for him with helicopter)
not intersecting barriers.

Mafia found you and give you task to program algorithm that finds the shortest path. Price is your life.

**Input**

NMKax ay bx by sx1 sy1 fx1 fy2 sx2 sy2 fx2 fy2 .... sxK syK fxK fyK

N — is *WEST*-EAST length, *M* — is *SOUTH*-NORTH length.
*K* is the number of barriers.

The firts line contains *N*, *M*, and *K*.
The second line contains coordinates of the points *A* and *B*.

K lines after the first two lines contain descriptions of barriers.

Coordinates are from [0, *N*] (x-coordinate) and [0, *M*] (y-coordinate).

**Output**
Two lines.
The first conains shortest path length.
The second — description of the path — word consisting of letters *N*, *S*, *W*, *E*, *i*.e.
instruction describing how Nickolay should go through the forest from *A* to *B*.

Output "*NO* SOLUTION" if there is now path from *A* to *B*.

Input#14 5 3 3 1 3 4 2 2 4 3 0 4 1 4 2 4 2 5 |
Output#17 WWNNEEN |

Input#24 5 3 3 1 3 4 2 2 4 3 0 4 1 4 2 2 2 3 |
Output#2NO SOLUTION |

**Author:
Andrey Ulanov, Personal Programming MIPT Contest, 7 October 2007
**

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