Problem 2534. Path of least resistance - Move all direction

Created by rifat

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>Extension of the wonderful</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://www.mathworks.com/matlabcentral/cody/problems/1049-path-of-least-resistance\"><w:r><w:t>Problem 1049</w:t></w:r></w:hyperlink><w:r><w:t> (Path of Least Resistance).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A matrix is given as input. You have to take a tour starting from the top left corner to the bottom right corner of the matrix. You can move to any one of the adjacent 8 elements. Return only the sum of the elements in your path.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example :</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[Input = [1 9 1 1\n         9 1 9 1\n         1 3 9 1\n         9 9 8 1];\n\nOutput = 7;]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Here, the least-sum path though the matrix is shown below with asterisk</w:t></w:r><w:r><w:t>(*</w:t></w:r><w:r><w:t>):</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[          [1* 9  1* 1*\n           9  1* 9  1*\n           1  3  9  1*\n           9  9  8  1*];]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Return only the sum of the elements along the path. I will add robust test cases time to time WITHOUT re-scoring existing solutions.</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

29 Solutions
15 Solvers

Last Solution submitted on Jul 20, 2020

Last 200 Solutions

Problem Comments

7 Comments

7 Comments

Show 4 older comments

Paul Berglund on 30 Aug 2014

I don't understand how this works with negative elements. For example if the input matrix is [0 -1;0 0] it is possible to obtain an arbitrarily low score by going [EastWest] sufficiently many times then EastSouth.

rifat on 30 Aug 2014

yeah... deleted the negative elements.. was foolish of me to think that way

Bogdan Doroslovac on 31 Aug 2014

The eye matrix is tricky - i must admit i cheated.. there is a of torugle with branching, i tried developing algorithm do "look up front" but failded...

Paul Berglund on 1 Sep 2014

I get 11 for test case 2.

rifat on 2 Sep 2014

May be you are considering the element at the bottom left corner. But, it is not necessary since diagonal movement is also allowed

Paul Berglund on 3 Sep 2014

OK, you're right about test case 2. I was wrong. But I get 6 for test case 1, not 7. The shortest path does not include upper right corner.

rifat on 4 Sep 2014

yeah, that is wrong.. corrected and thanks. too many mistake in a single problem

Problem Recent Solvers15

Problem Tags

optimization

Problem 2534. Path of least resistance - Move all direction

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers15

Suggested Problems

More from this Author44

Problem Tags

Problem 2534. Path of least resistance - Move all direction

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers15

Suggested Problems

More from this Author44

Problem Tags

Players