Problem 1944. GJam 2014 China Rd B: Dragon Maze

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This Challenge is derived from</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://code.google.com/codejam/contest/2929486/dashboard#s=p3\"><w:r><w:t>GJam 2014 China Dragon Maze</w:t></w:r></w:hyperlink><w:r><w:t>. Small Case.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> [VEE] [M], VEE is 1x4 [ENx,ENy,EXx,EXy], Matrix (NRxNC &lt;=10).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> [P] maximum Points. If Impossible P=-1;</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Examples:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[[VEE] [M] [P]\n[0 2 3 2][-1 1 1 2;1 1 1 1;2 -1 -1 1;1 1 1 1] [7]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Contest Performance:</w:t></w:r><w:r><w:t> Best Delta Time of 17 minutes with 336 of 2010 able to process the small data set.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Strategy:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[1) Check Start/Finish path existence while creating path distances from start. (Suggest offset by +1 to match array). \n2) A ring of Zeros around the array may simplify processing.\n3) 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.]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This Challenge is derived from <a href = "http://code.google.com/codejam/contest/2929486/dashboard#s=p3">GJam 2014 China Dragon Maze</a>. 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 &lt;=10).Output: [P] maximum Points. If Impossible P=-1;Examples:<pre class="language-matlab">[VEE] [M] [P]
[0 2 3 2][-1 1 1 2;1 1 1 1;2 -1 -1 1;1 1 1 1] [7]
</pre>Contest Performance: Best Delta Time of 17 minutes with 336 of 2010 able to process the small data set.Strategy:<pre class="language-matlab">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.
</pre>

This Challenge is derived from <http://code.google.com/codejam/contest/2929486/dashboard#s=p3 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.

Solve

Solution Stats

12 Solutions
7 Solvers

Last Solution submitted on Apr 12, 2023

Last 200 Solutions

Solution Comments

Show comments

Problem Recent Solvers7

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1944. GJam 2014 China Rd B: Dragon Maze

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers7

Suggested Problems

More from this Author260

Problem Tags

Community Treasure Hunt

Problem 1944. GJam 2014 China Rd B: Dragon Maze

Solution Stats

Last 200 Solutions

Solution Comments

Problem Recent Solvers7

Suggested Problems

More from this Author260

Problem Tags

Community Treasure Hunt

Players