-1
$\begingroup$

I came across this question in a job interview and I couldn't solve it.

In a n*m matrix some cells are blocked.The robot can only move in direction of (x-1,y+2) or (x+2,y-1). Is it possible to reach B from A? If yes how many minimum paths exists?

$\endgroup$
1

1 Answer 1

0
$\begingroup$

First, we can get an early rejection: if (A.y - B.y) + (B.x - A.x) modulo 3 is non-zero, B is not reachable from A, regardless of where the obstacles may be. (Try drawing the cells you can reach via sequences of those two moves. They form a set of parallel diagonal lines, leaving gaps of unreachable cells in between)

Similarly, if 2(A.y - B.y) > (B.x - A.x), B is again not reachable from A. The only way we can decrease our Y is by increasing our X by twice as much, making anything below the line $\Delta y = -\frac 1 2 \Delta x$ unreachable.

That quickly rules out two thirds or more of the matrix for us.

If B is potentially reachable according to the test above, then a simple way to find one/all minimum paths to it (if any exist) is using breadth-first search.

Execute your graph search from A, taking only the moves (x-1, y+2) or (x+2, y-1) from each cell, and aborting any move that takes you to a blocked cell. Record for each cell you reach this way the number of hops it took to get there (ie. the number you recorded for the cell you reached it from, +1, with A having the value 0)

If the search terminates (has no new reachable cells to visit) without ever visiting B, you can conclude that B is not reachable from A.

If you reach B, stop. The value you write here is the length of a minimal path.

Now you can retrace your steps to count the paths. There are two possible cells that could have reached B. You can tell if they're part of a minimal path by checking if the hop count to reach that cell is exactly 1 less than the hop count to reach B. (Since breadth-first search iterates cells in non-decreasing order of hop count, you can be sure all possible stepping stones to reach B have been written to before B).

You can repeat this recursively to find the hops that lead to those penultimate cells, and the hops that lead to their predecessors, all the way back to A. Summing the routes you find at each stage gives you the total number of minimal paths - and you can even exhibit all of them if you like.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.