Stephen has wandered away from the harbour and discovered a spooky old house in the woods. After exploring it, he found that the house has 16 ( 4x4 ) rooms. Each room has four doors, but some of those doors are blocked off, and the outer doors lead into the darkness. The only exit from the house is the northern door in the 1st room. While exploring the last room (#16) he heard a haunting groan followed by a grinding noise and the sound of chains rattling. He started a sensor sweep of the house and discovered that a ghost had appeared in the first (#1) room. Terrified, Stephen now turns to you to help him escape the house. You'll both need to make it to the first room without encountering the ghost, for if you meet it, bad things may happen...

The two of you can move in four possible directions: north, south, west and east ("N", "S", "W", "E") as long as the doors are not blocked off. Stephen is scared and cannot stand still. You'll need to make sure that he doesn't try to escape by any of the other outer doors as he will certainly fall into the dark abyss. The only safe way out of the house through the northern door in first room. On each step you should return a direction as a letter, telling Stephen where you want him to move. After he takes a step, the ghost will make its move. The ghost knows where you and Stephen are, and is actively trying to catch you. It cannot sit still and will always try to take the shortest path to where you and Stephen are, but it is little dumb and uses the Euclidean distance to decide which direction to move in. If multiple directions are tied for best direction, then the ghost will randomly choose between those best directions. You are limited to 30 moves, after that, the ghost summons his friends and will capture you both...

On each step you are given three arguments: the map of the house, Stephens location (room number) and the Ghosts location (room number). The map is represented as a list with 16 elements, where each element corresponds to a room (1st element -- 1st room). Each element on the list is a string with blocked directions. For example: If the 6th element (index 5) is "NS", then in the 6th room the north and south doors are blocked.
Be careful: Outer doors are always unblocked. You should exit only through the north door in the 1st room.

Input: The map of the house as a list of strings, Stephen's location (room number) and the Ghost's location (room number) as integers.

Output: Stephan's move as a string.

checkio(
    ["", "S", "S", "",
     "E", "NW", "NS", "",
     "E", "WS", "NS", "",
     "", "N", "N", ""],
    16, 1)
checkio(
    ["", "", "", "",
     "E", "ESW", "ESW", "W",
     "E", "ENW", "ENW", "W",
     "", "", "", ""],
    11, 6)

How it is used: This task is useful to train your path finding abilities and gaming algorithms. Unlike ordinary pathfinding problems, here you need to take into account the actions of the artificial intelligence. This concept is required for complex navigational systems in a changing environment.

Precondition:
0 < stephen ≤ 16
0 < ghost ≤ 16
len(house) == 16