Problem 2617. Yet Another Path Finder

Created by rifat in Community

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.


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

75.0% Correct | 25.0% Incorrect
Last solution submitted on Feb 22, 2019

Problem Comments

Recent Solvers6

Suggested Problems

More from this Author45