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 :)
3351 Solvers
Find relatively common elements in matrix rows
630 Solvers
Given an unsigned integer x, find the largest y by rearranging the bits in x
514 Solvers
Create a random logical vector of N elements of which M are true.
75 Solvers
Is this triangle right-angled?
1311 Solvers