Find maximum length of good path in a grid

Question

Given is a N*N grid.Now we need to find a good path of maximum length , where good path is defined as follow :

1. Good path always start from a cell marked as 0
2. We are only allowed to move Left,Right,Up Or Down
3. If the value of ith cell is say A, then value of next cell in the path must be A+1.

Now given these few conditions, I need to find out the length of maximum path that can be made. Also I need to count such paths that are of maximum length.

Example : Let N=3 and we have 3*3 matrix as follow :

0 3 2               
3 0 1               
2 1 0            

Then maximum good path length here is 3 and the count of such good paths is 4.

0 3 2
3 0 1
2 1 0

0 3 2
3 0 1
2 1 0

0 3 2
3 0 1
2 1 0

0 3 2
3 0 1
2 1 0

Answer 1

This problem is a variation of Longest Path Problem, however your restrictions make this problem much easier, since the graph is actually a Directed Acyclic Graph (DAG), and thus the problem is solveable efficiently.

Define the directed graph G=(V,E) as following:

• V = { all cells in the matrix} (sanity check: |V| = N^2)
• E = { (u,v) | u is adjacent to v AND value(u) + 1 = value(v) }

Note that the resulting graph from the above definition is a DAG, because you cannot have any cycles, since it will result in having some edge e= (u,v) such that value(u) > value(v).

Now, you only need to find longest path in a DAG from any starting point. This is done by topological sort on the graph, and then using Dynamic Programming:

init:
for every source in the DAG:
D(v) = 0            if value(v) = 0
       -infinity    otherwise
step:
for each node v from first to last (according to topological sort)
   D(v) = max{D(u) + 1 | for each edge (u,v) }

When you are done, find the node v with maximal value D(v), this is the length of the longest "good path".
Finding the path itself is done by rerolling the above, retracing your steps back from the maximal D(v) until you reach back the initial node with value 0.

Complexity of this approach is O(V+E) = O(n^2)

---

Since you are looking for the number of longest paths, you can modify this solution a bit to count the number of paths reached to each node, as follows:

Topological sort the nodes, let the sorted array be arr (1)
For each node v from start to end of arr:
   if value(v) = 0:
        set D(v) = 1 
   else
        sum = 0
        for each u such that (u,v) is an edge: (2)
            sum = sum + D(u) 
        D(v) = sum

The above will find you for each node v the number of "good paths" D(v) that reaches it. All you have to do now, is find the maximal value x that has sum node v such that value(v) = x and D(v) > 0, and sum the number of paths reaching any node with value(v):

max = 0
numPaths = 0
for each node v:
    if value(v) == max:
         numPaths = numPaths + D(v)
    else if value(v) > max AND D(v) > 0:
         numPaths = D(v)
         max = value(v)
return numPaths

Notes: (1) - a "regular" sort works here to, but it will take O(n^2logn) time, and topological sort takes O(n^2) time
(2) Reminder, (u,v) is an edge if: (1) u and v are adjacent (2) value(u) + 1 = value(v)