Problem 1049. Path of least resistance

Created by Paul Peeling

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>Find the length of the shortest path through the matrix from the top left to bottom right corner. You may move right, down, or diagonally right-down one element at a time. The length of the path is the sum of the elements you pass through.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>E.g.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ M = [*8      6      10      10     4     7     7      7\n       9     *1      10      5      9     0     8      2\n       1      3     *2       8      8     8     7      7\n       9      5      10     *1     *10   *9    *4     *0 ]; \n\n>> shortest_path(M)\n\nans =\n\n      35]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The shortest path through this matrix has length 35. Each element along the path is marked with a</w:t></w:r><w:r><w:t> *</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>"}]}

Solve

Solution Stats

111 Solutions
66 Solvers

Last Solution submitted on Jul 20, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Zikobrelli on 10 Feb 2014

Cool problem. Optimal solutions sometimes appear if moving up is enabled.

Solution Comments

Solution 167237

4 Comments

4 Comments

Show 1 older comment

Vitaly Lavrukhin on 23 Nov 2012

functional programming approach

Jean-Marie Sainthillier on 8 Sep 2013

Congratulations.
Honestly, I have difficulties with this kind of algorithm. I have the feeling that you only increment i or j, but at the end you check all the matrix.

Vitaly Lavrukhin on 9 Sep 2013

Thanks, Jean-Marie. This solution uses recursive calls of the function. So all elements of the matrix are processed.
If you would like to learn more about functional programming principles, I recommend 'Functional Programming Principles in Scala' course by Martin Odersky at Coursera. It starts soon. Actually, I wrote this solution after taking the course a year ago. It is very interesting to look at the same problem from different points of view.

Jean-Marie Sainthillier on 10 Sep 2013

Thanks for your advice.

Problem Recent Solvers66

Problem Tags

dynamic-programming

Problem 1049. Path of least resistance

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers66

Suggested Problems

More from this Author5

Problem Tags

Problem 1049. Path of least resistance

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers66

Suggested Problems

More from this Author5

Problem Tags

Players