CODEWITHSUNDEEP
javac++algorithm
amendeep singh
amendeep singh

Reputation: 15

Finding a path whose elements sum up to a given number in a matrix

Given a M x N matrix and a positive integer p, how can I find a continuous path recursively through the matrix starting at position 0,0 that will sum to p? You can move left (col - 1), right (col + 1), up (row - 1) or down (row + 1), and can only use a position once in the path. If there is such path in the matrix, output it in a separate matrix with the same shape, by filling the positions on the path with 1 and the rest positions with 0.

I literally froze and could do anything, is there any technique for solving these kinds of problems? How would one go on about approaching this problem, a solution would be much appreciated.

Here is an example where p = 73:

2  8  15 
1  10 5
19 19 3  
5  6  6
2  8  2

Output:

1  0  0
1  0  0
1  1  1
1  1  1
1  1  1

Upvotes: 0

Views: 1203

Answers (1)

DavidW
DavidW

Reputation: 1421

"Should randomly move" is (possibly intentionally) misleading. What you want to do is effectively a depth-first search, systematically testing possible routes. A route terminates if it equals (you're done) or exceeds the target number, in which case you back up.

If we assume the route can't double back on itself (you didn't say), then what would work is a left- (or right-) edge following pattern, like a standard maze solver. So at each new node visited, it proceeds to the left-most non-visited adjacent node, subsequently trying other adjacent nodes in a clockwise direction.

(If the route can revisit nodes, then treat the matrix as a 4-tree and pick an arbitrary direction to test first.)

Upvotes: 1

Related Questions