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

83.33% Correct | 16.67% Incorrect
Last Solution submitted on Apr 12, 2023

Solution Comments

Show comments

Problem Recent Solvers7

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!