Problem
Recently I came across this problem of matrix-traversal where I have to find a path from the starting index to last index. Here what I needed to do is to find whether path exists or not. Matrix is full of '0's and '1's. '1' means you could not go forward. '0' means you could go forward. You could move 'right', 'left', 'up' or 'down'. No diagonal moves allowed.
My Approach
Initially I could not decode this because I had only 10 minutes to provide a solution for this. My thought process was just as a usual programmer. I was thinking imperatively. My initial matrix looked like this.
I was trying to run two-loops (loop inside a loop). But could not get the thing done with the given time. Then after my assignment I tried to solve this again. I found a solution which has the basic traversal with forward moves (go-right and go-down). And one of the main concern was I could not do back-tracking (go-left or go-up).
In my assignment I was given a hint to think on this with regards to recursion. So, I started to rethink with recursion.
Recursive Solution
So, if you think recursively you have to think in a way to divide this problem into smaller pieces of it-self. What we could divide is the matrix. Initially I was miss-guided to think that I will have to divide this
matrix physical (I mean actually create a partial matrix from the
current matrix). But later I identified this division should be logical.
If you go through the above diagram. You might see that the logical division of initial matrix would look similar to it. If the right-cell is not blocked traversal could do via right-move. If right-cell is blocked but cell below the initial-cell is not blocked then we could proceed through down-move traversal. If both of them are blocked then we do not have a move.
Lets think that move-down is possible. Then our latest logical matrices would be like follows.
If you think in this way you might see that if you move forward there will be four logical matrices created when you consider all the moves possible.
You might notice that there are two new logical matrices which we could identify here. Namely we have Left-Move and Move-Up (mainly for back-tracking purposes). Following would be my recursive algorithm.
Imperative Solution
When we thinking about a recursive solution we are always in danger with stack-overflow or out-of-memory due to the depth of function calls could recur (check here for more information). So, it is better to implement an imperative solution to a problem rather than a recursive solution.
So, I tried to improve my initial solution (with imperative approach) which has two for-loops.
In the above algorithm you could see that there is a problem. You could not back-track (in other words you could not go up or left). Issue here is with the structure of the for-loop and the logic I was thinking about the proceeding to next position of the matrix.
So, what I thought was mixing dynamic matrix manipulation (updating traversing-matrix dynamically) & integrating traversing logic of recursive algorithm.
The key difference here is I have replaced the for-loops with while-loops. And the logical matrix which the loop is operating will be changed dynamically.
Java Implementation for above algorithm could be found here.
