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.

Solution Stats

88.89% Correct | 11.11% Incorrect
Last Solution submitted on Dec 08, 2018

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers3

Suggested Problems

More from this Author308

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!