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]
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 :)
Find the sum of all the numbers of the input vector
33456 Solvers
1420 Solvers
Check to see if a Sudoku Puzzle is Solved
374 Solvers
271 Solvers
2267 Solvers