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.
17123 Solvers
the fly, the train, the second train, and their Zeno's paradox
55 Solvers
152 Solvers
Side of an equilateral triangle
1516 Solvers
1391 Solvers
Problem Tags