Problem 1944. GJam 2014 China Rd B: Dragon Maze
This Challenge is derived from GJam 2014 China Dragon Maze. Small Case.
The Goal is determine the optimal minimum distance path that maximizes score. Multiple minimum distance paths may exist. Output the score for the path that maximizes the cumulative sum of the path.
The input is a vector of Entrance/Exit [ENx,ENy,EXx,EXy] and a Matrix of Points. The Matrix and Entrance/Exit are zero based (Top Left is (0,0)). Entrance and Exit will be valid. A [-1] in the matrix is a Wall that can not be traversed. Movement is limited to NSEW, no diagonals.
Input: [VEE] [M], VEE is 1x4 [ENx,ENy,EXx,EXy], Matrix (NRxNC <=10).
Output: [P] maximum Points. If Impossible P=-1;
Examples:
[VEE] [M] [P] [0 2 3 2][-1 1 1 2;1 1 1 1;2 -1 -1 1;1 1 1 1] [7]
Contest Performance: Best Delta Time of 17 minutes with 336 of 2010 able to process the small data set.
Strategy:
1) Check Start/Finish path existence while creating path distances from start. (Suggest offset by +1 to match array). 2) A ring of Zeros around the array may simplify processing. 3) My preference is to work from Finish to Start while tracking best scores for the Kth distance from the Start. A few tricks here to only check for valid prior values.
Solution Stats
Solution Comments
Show commentsProblem Recent Solvers7
Suggested Problems
-
4512 Solvers
-
Return unique values without sorting
913 Solvers
-
We love vectorized solutions. Problem 1 : remove the row average.
815 Solvers
-
14546 Solvers
-
Factorial: Unlimited Size : java.math
42 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!