Problem 1903. GJam 2014 China Rd A: Maze with a Left Hand Rule

This Challenge is derived from GJam 2014 China Cross the Maze.

The Goal is to minimally traverse a Maze from a Starting Point to Finish Point in less than 10,000 moves where the Bot can only go forward and must maintain its Left Arm in contact with a wall. At the Start Point the Bot can only touch NSEW. After the first move the Bot maintains contact on diagonals. Rotations in a cul-de-sac or turning are not counted as moves.

Input: [M, Start_Finish] where M is an NxN (0,1=Wall) array and Start_Finish is [Sr,Sc,Fr,Fc]

Output: Path, a string of Movements {N,S,E,W}. If Path is >10,000 moves or No solution return a null string.

Examples:

.##.#
.....
...#.
.###.
...#.
1 1 5 3

Note: (1,1) is Top Left and start point for this case.

The # are replaced by 1s and '.' will be 0s.

Output: SEEENSESSSNNNWWSWWSSEE

Contest Performance: Best Delta Time of 17 minutes with only 134 correct solutions in 3 hours.