Problem 283. Give the Shortest Path Through The Maze

Created by @bmtran (Bryant Tran)

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:rPr><w:b/></w:rPr><w:t>Description</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The purpose of this problem is to give the shortest path through a maze. The maze will be provided in a codified matrix of size</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>M</w:t></w:r><w:r><w:t> x</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> where each element of the matrix represents a place in the grid and the value of each element is a binary-code that represents the presence of walls. That is:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ + +\n value = 0 -> 00 -> no walls -> \n NW + + \n\n + +\n value = 1 -> 01 -> wall to W -> |\n NW + +\n\n +---+\n value = 2 -> 10 -> wall to N -> \n NW + +\n\n +---+\n value = 3 -> 11 -> walls to N and W -> |\n + +]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:i/></w:rPr><w:t>Note: all outer boundaries are walls. My test cases provide for this already. You do</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t> </w:t></w:r><w:r><w:rPr><w:b/><w:i/></w:rPr><w:t>not</w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t> need to account for this.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The path will always start at the NorthWest corner (subscript</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>(1,1)</w:t></w:r><w:r><w:t>) and end at the SouthEast corner (subscript</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>(M,N)</w:t></w:r><w:r><w:t>). The output should be a matrix of the same size as the input matrix that lists the steps you need to go through to traverse the maze with the remaining squares being 0. For example,</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ path = [ 1 2 0 0 0 0 \n 4 3 0 9 10 0\n 5 6 7 8 11 0 \n 0 0 0 0 12 13 ]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>which represents an output solution that is 13 units long. As you can see, the NorthWest corner will always be 1 and the SouthEast corner will always be the length of your path.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You are</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>NOT</w:t></w:r><w:r><w:t> guaranteed that there will be only one shortest path for the test cases. If there exist multiple shortest paths, you must represent them all. It can easily be shown that the superposition of two shortest paths will never lead to a multi-valued element in the output matrix.</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>Example</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Input maze:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ maze = [ 3 2 2 2 3\n 1 3 2 2 3\n 1 3 2 3 1\n 1 1 0 2 0\n 1 0 2 1 1 ];]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Graphical Representation:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ +---+---+---+---+---+\n | | |\n + +---+---+---+---+\n | | | |\n + +---+---+---+ +\n | | | | |\n + + + +---+ +\n | | |\n + + +---+ + +\n | | | |\n +---+---+---+---+---+]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Solution:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ soln = [ 1 0 0 0 0\n 2 0 0 0 0\n 3 0 0 0 0\n 4 7 8 9 10\n 5 6 0 0 11 ]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Graphical Representation:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ +---+---+---+---+---+\n | 1 | |\n + +---+---+---+---+\n | 2 | | |\n + +---+---+---+ +\n | 3 | | | |\n + + + +---+ +\n | 4 | 7 8 9 10 |\n + + +---+ + +\n | 5 6 | |11 |\n +---+---+---+---+---+]]></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>"}]}

DescriptionThe purpose of this problem is to give the shortest path through a maze. The maze will be provided in a codified matrix of size M x N where each element of the matrix represents a place in the grid and the value of each element is a binary-code that represents the presence of walls. That is:<pre> + +
 value = 0 -> 00 -> no walls -> 
 NW + + </pre><pre> + +
 value = 1 -> 01 -> wall to W -> |
 NW + +</pre><pre> +---+
 value = 2 -> 10 -> wall to N -> 
 NW + +</pre><pre> +---+
 value = 3 -> 11 -> walls to N and W -> |
 + +</pre>Note: all outer boundaries are walls. My test cases provide for this already. You do not need to account for this.The path will always start at the NorthWest corner (subscript <tt>(1,1)</tt>) and end at the SouthEast corner (subscript <tt>(M,N)</tt>). The output should be a matrix of the same size as the input matrix that lists the steps you need to go through to traverse the maze with the remaining squares being 0. For example,<pre> path = [ 1 2 0 0 0 0 
 4 3 0 9 10 0
 5 6 7 8 11 0 
 0 0 0 0 12 13 ]</pre>which represents an output solution that is 13 units long. As you can see, the NorthWest corner will always be 1 and the SouthEast corner will always be the length of your path.You are NOT guaranteed that there will be only one shortest path for the test cases. If there exist multiple shortest paths, you must represent them all. It can easily be shown that the superposition of two shortest paths will never lead to a multi-valued element in the output matrix.ExampleInput maze:<pre> maze = [ 3 2 2 2 3
 1 3 2 2 3
 1 3 2 3 1
 1 1 0 2 0
 1 0 2 1 1 ];</pre>Graphical Representation:<pre> +---+---+---+---+---+
 | | |
 + +---+---+---+---+
 | | | |
 + +---+---+---+ +
 | | | | |
 + + + +---+ +
 | | |
 + + +---+ + +
 | | | |
 +---+---+---+---+---+</pre>Solution:<pre> soln = [ 1 0 0 0 0
 2 0 0 0 0
 3 0 0 0 0
 4 7 8 9 10
 5 6 0 0 11 ]</pre>Graphical Representation:<pre> +---+---+---+---+---+
 | 1 | |
 + +---+---+---+---+
 | 2 | | |
 + +---+---+---+ +
 | 3 | | | |
 + + + +---+ +
 | 4 | 7 8 9 10 |
 + + +---+ + +
 | 5 6 | |11 |
 +---+---+---+---+---+</pre>

*Description*

The purpose of this problem is to give the shortest path through a maze. The maze will be provided in a codified matrix of size _M_ x _N_ where each element of the matrix represents a place in the grid and the value of each element is a binary-code that represents the presence of walls. That is:

+   +
    value = 0 -> 00 -> no walls         -> 
                 NW                        +   +

+   +
    value = 1 -> 01 -> wall to W        -> |
                 NW                        +   +
                                           
                                           +---+
    value = 2 -> 10 -> wall to N        -> 
                 NW                        +   +

+---+
    value = 3 -> 11 -> walls to N and W -> |
                                           +   +

_Note: all outer boundaries are walls. My test cases provide for this already. You do *not* need to account for this._

The path will always start at the NorthWest corner (subscript |(1,1)|) and end at the SouthEast corner (subscript |(M,N)|). The output should be a matrix of the same size as the input matrix that lists the steps you need to go through to traverse the maze with the remaining squares being 0. For example,

path = [  1   2   0   0   0   0 
              4   3   0   9  10   0
              5   6   7   8  11   0 
              0   0   0   0  12  13 ]

which represents an output solution that is 13 units long. As you can see, the NorthWest corner will always be 1 and the SouthEast corner will always be the length of your path.

You are *NOT* guaranteed that there will be only one shortest path for the test cases. If there exist multiple shortest paths, you must represent them all. It can easily be shown that the superposition of two shortest paths will never lead to a multi-valued element in the output matrix.

*Example*

Input maze:

maze = [  3  2  2  2  3
              1  3  2  2  3
              1  3  2  3  1
              1  1  0  2  0
              1  0  2  1  1  ];
    
Graphical Representation:

+---+---+---+---+---+
    |               |   |
    +   +---+---+---+---+
    |   |           |   |
    +   +---+---+---+   +
    |   |       |   |   |
    +   +   +   +---+   +
    |   |               |
    +   +   +---+   +   +
    |           |   |   |
    +---+---+---+---+---+

Solution:

soln = [  1   0   0   0   0
              2   0   0   0   0
              3   0   0   0   0
              4   7   8   9  10
              5   6   0   0  11 ]

Graphical Representation:

+---+---+---+---+---+
    | 1             |   |
    +   +---+---+---+---+
    | 2 |           |   |
    +   +---+---+---+   +
    | 3 |       |   |   |
    +   +   +   +---+   +
    | 4 | 7   8   9  10 |
    +   +   +---+   +   +
    | 5   6     |   |11 |
    +---+---+---+---+---+

Solve

Solution Stats

394 Solutions
41 Solvers

Last Solution submitted on Nov 29, 2021

Last 200 Solutions

Problem Comments

Solution Comments

Solution 35801

1 Comment

1 Comment

@bmtran (Bryant Tran) on 10 Feb 2012

wow, this is the most amazing MATLAB BFS implementations i've ever seen, and you're doing it with 2 roots at once. I'm seriously impressed. also, using sparse to make the graph from the maze matrix is genius

Solution 35546

1 Comment

1 Comment

@bmtran (Bryant Tran) on 9 Feb 2012

i am no match for your usage of the "sparse" function. I really need to learn more about it.

Problem Recent Solvers41

Problem Tags

Community Treasure Hunt

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

Start Hunting!