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.
Solution Stats
Solution Comments
Show commentsProblem Recent Solvers3
Suggested Problems
-
17068 Solvers
-
Back to basics 22 - Rotate a matrix
901 Solvers
-
485 Solvers
-
Remove the two elements next to NaN value
650 Solvers
-
Replace all zeros and NaNs in a matrix with the string 'error'
99 Solvers
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!