Problem 1122. USC Fall 2012 ACM: Rover Maze

This Challenge is to solve Question F, Martian Pits, of the USC ACM Fall 2012 Contest.

The task is to determine the minimum time for the Rover to drive from its current position to a Goal location. The Rover must STOP on the Goal location. Commands are processed at 1 Cmd per sec. Rover must stay on array.

This is an intriguing Maze problem that incorporates turn penalties, variable speed forward, and a fixed reverse speed.

Initial conditions are Rover Stopped and Facing +Y.
Commands are processed at 1 second intervals

Commands and their attributes:
FORWARD: Starts rolling forward at 1 cm/s
BACKWARDS: Roll backwards at 1 cm/s
FASTER: Increase forward speed by 1 cm/s up to 5 cm/s
SLOWER: Decrease forward speed by 1 cm/s down to 0 cm/s. At 0 cm/s Rover is "Stopped"
STOP: Halts rover movement
RIGHT: Turn rover 90 degrees to the right
LEFT: Turn the rover 90 degrees to the left
NOOP: No change in anything 

Commands FORWARD, BACKWARDS, RIGHT, LEFT only take effect if the rover is stopped. A moving rover ignores these commands.

Commands FASTER and SLOWER only take effect if the rover is moving forward.

Input: [Char array] "." is Flat ground, "P" Pit, "R" Rover start location, "D" is Destination. Matrix max dim 50, min 1.

Output: [T]; Drive Time to destination; -1 if not possible

Scoring: Time (msec)

The full USC data file

Example:

Input: [A]

...................D
.P......P.P.........
.P...PPPP.P.........
.P...P....P.........
.P...P.PPPP.........
.P.PPP.P............
.P.P...P............
.PPP.PPPPPPPPPPPPPPP
....R...............
PPPPPPPPPPPPPPPPPPPP

Output: [19] as the best path is L, Fwd, Faster, Slower, Stop to (9,1). The cmds to reach (1,1) are R, Fwd, Faster, Faster, Slower, Stop. Cmds to optimally reach (1,20) are R, Fwd, Faster, Faster, Faster, Faster, Slower, Stop.

Once again my code is large thus the contest will be scored based on Processing Time.

Hints: One Speed-Up method is to do an initial Start/Finish connectivity check.

Martian Pits C solution. Time to Solve: 40 minutes. Only three solved this puzzle during the contest. Start.