There are cycles in recursion,there is no recursion tree over here, which
can be traversed in bottom up fashion,so no DP.
Shortest path algorithms will be the answer
On Mon, Oct 31, 2011 at 9:30 PM, Don wrote:
> Use a path cost matrix of the same size as the given matrix. Set all
> locations to
Use a path cost matrix of the same size as the given matrix. Set all
locations to a maximum cost value.
Use a queue to store locations which still need to be processed.
Start by setting the cost to the destination equal to the cost of that
location and adding that location to the queue.
Then, while
You can convert this into a regular SP problem on a graph and use a
classical SP algorithm.
In this graph, the nodes are labeled with pairs (i,j). If M[A,B] is
your matrix, then the graph's adjacency matrix C[A,B] is just
C[ (iA, jA), (iB, jB) ] = {
M[ iB, jB ] if abs(iA-iB) <= 1 && abs(jA-jB)
