Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Problem 1944. GJam 2014 China Rd B: Dragon Maze

Created by Richard Zapor

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.

Tags

Problem Group

Solution Statistics

6 correct solutions 0 incorrect solutions
Last solution submitted on Oct 26, 2013