Problem 2617. Yet Another Path Finder
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:
M =
[2 3 3 6 7 10 10 11] r = 3 c = 4
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]
Solution Stats
Problem Comments
-
3 Comments
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)...
Yes.. totally screwed up in test 1, 4 and 7. Will fix within today.. thanks
Fixed the test suite and example in the statement. Looks clean now :)
Solution Comments
Show commentsProblem Recent Solvers28
Suggested Problems
-
1181 Solvers
-
Magic is simple (for beginners)
9320 Solvers
-
Convert a Cell Array into an Array
1805 Solvers
-
Matrix multiplication across rows
332 Solvers
-
331 Solvers
More from this Author44
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!