Problem 2617. Yet Another Path Finder

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>Assume there is a rectangular grid of points. These points are indicated by linear indices in a MATLAB-fashion. Some of the grid points are connected by vertical or horizontal lines. Your task is to find a path through the points which are not connected or touched by any line starting from the top left to the bottom right corner. One additional difficulty is that you can not move diagonally. That means the valid paths should only contain horizontal and vertical moves. There exists only one unique path. You cannot go through a particular path more than once.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A matrix M of size N-by-2 will be given containing the grid information. Each row of M indicates two grid points which are connected by a line. Return a vector containing the linear indices of points in the grid that forms a valid path. The second (r) and third (c) input indicates the row and column size of the grid.</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[M =\n\n[2 3\n 3 6\n 7 10\n 10 11]\nr = 3\nc = 4]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Grid points 2-3, 3-6, 7-10 and 10-11 are connected by lines. Thus the only path though which you can navigate is that formed by grid points 1,4,5,8,9 and 12. Thus return [1 4 5 8 9 12]</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>"}]}

Assume there is a rectangular grid of points. These points are indicated by linear indices in a MATLAB-fashion. Some of the grid points are connected by vertical or horizontal lines. Your task is to find a path through the points which are not connected or touched by any line starting from the top left to the bottom right corner. One additional difficulty is that you can not move diagonally. That means the valid paths should only contain horizontal and vertical moves. There exists only one unique path. You cannot go through a particular path more than once.A matrix M of size N-by-2 will be given containing the grid information. Each row of M indicates two grid points which are connected by a line. Return a vector containing the linear indices of points in the grid that forms a valid path. The second (r) and third (c) input indicates the row and column size of the grid.Example:<pre class="language-matlab">M =
</pre><pre class="language-matlab">[2 3
 3 6
 7 10
 10 11]
r = 3
c = 4
</pre>Grid points 2-3, 3-6, 7-10 and 10-11 are connected by lines. Thus the only path though which you can navigate is that formed by grid points 1,4,5,8,9 and 12. Thus return [1 4 5 8 9 12]

Solve

Solution Stats

23 Solutions
13 Solvers

Last Solution submitted on Nov 29, 2020

Last 200 Solutions

Problem Comments

3 Comments

3 Comments

Alfonso Nieto-Castanon on 6 Oct 2014

In the example, and in the first problem of the testsuite, perhaps it should read r=3; c=3 (instead of r=3; c=4)? Also some of the testsuite problems seem to have multiple solutions (non-unique shortest-path solution)...

rifat on 6 Oct 2014

Yes.. totally screwed up in test 1, 4 and 7. Will fix within today.. thanks

rifat on 6 Oct 2014

Fixed the test suite and example in the statement. Looks clean now :)

Problem Recent Solvers13

Problem Tags

graph grid path

Community Treasure Hunt

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

Start Hunting!

Problem 2617. Yet Another Path Finder

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers13

Suggested Problems

More from this Author44

Problem Tags

Community Treasure Hunt

Problem 2617. Yet Another Path Finder

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers13

Suggested Problems

More from this Author44

Problem Tags

Community Treasure Hunt

Players