Find maximum length of good path in a grid

问题:

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

回答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)

回答2:

You can do this with a simple Breadth-First Search.

First find all cells marked 0. (This is O(N²).) On each such cell put a walker. Each walker carries a number 'p' initialized to 1.

Now iterate:

All walkers stand on cells with the same number k. Each walker looks for neighboring cells (left, right, up or down) marked with k+1.

If no walker sees such a cell, the search is over. The length of the longest path is k, and the number of such paths is the sum of the p's of all the walkers.

If some walkers see such numbers, kill any walkers that don't.

Each walker moves into a good neighboring cell. If a walker sees more than one good cell, it divides into as many walkers as there are good cells, and one goes into each. (Each "child" has the same p value its "parent" had.) If two or more walkers meet in the same cell (i.e. if more than one path led to that cell) then they combine into a single walker, whose 'p' value is the sum of their 'p' values.

This algorithm is O(N²), since no cell can be visited more than once, and the number of walkers cannot exceed the number of cells.

回答3:

I did it using ActionScript, hope it's readable. I think it is working correctly but I may have missed something.

const N:int = 9; // field size
const MIN_VALUE:int = 0; // start value

var field:Array = [];

// create field - not relevant to the task
var probabilities:Array = [0,1,2,3,4,5];
for (var i:int = 0; i < N * N; i++) field.push(probabilities[int(Math.random() * probabilities.length)]);//RANGE));
print_field();

// initial chain fill. We will find any chains of adjacent 0-1 elements.
var chain_list:Array = [];
for (var offset:int = 0; offset < N * N - 1; offset++) {
    if (offset < N * N - N) { // y coordinate is not the lowest
        var chain:Array = find_chain(offset, offset + N, MIN_VALUE);
        if (chain) chain_list.push(chain);
    }
    if ((offset % N) < N - 1) { // x coordinate is not the rightmost
        chain = find_chain(offset, offset + 1, MIN_VALUE);
        if (chain) chain_list.push(chain);
    }
}

var merged_chain_list:Array = chain_list;
var current_value:int = MIN_VALUE + 1;

// for each found chain, scan its higher end for more attached chains
// and merge them into new chain if found
while(chain_list.length) {
    chain_list = [];
    for (i = 0; i < merged_chain_list.length; i++) {
        chain = merged_chain_list[i];
        offset = chain[chain.length - 1];

        if (offset < N * N - N) {
            var tmp:Array = find_chain(offset, offset + N, current_value);
            if (tmp) chain_list.push(merge_chains(chain, tmp));
        }
        if (offset > N) {
            tmp = find_chain(offset, offset - N, current_value);
            if (tmp) chain_list.push(merge_chains(chain, tmp));
        }
        if ((offset % N) < N - 1) {
            tmp = find_chain(offset, offset + 1, current_value);
            if (tmp) chain_list.push(merge_chains(chain, tmp));
        }
        if (offset % N) {
            tmp = find_chain(offset, offset - 1, current_value);
            if (tmp) chain_list.push(merge_chains(chain, tmp));
        }
    }

    //save the last merged result if any and try the next value
    if (chain_list.length) {
        merged_chain_list = chain_list;
        current_value++;
    }
}

// final merged list is a list of chains of a same maximum length
print_chains(merged_chain_list);

function find_chain(offset1, offset2, current_value):Array {
    // returns always sorted sorted from min to max
    var v1:int = field[offset1];
    var v2:int = field[offset2];
    if (v1 == current_value && v2 == current_value + 1) return [offset1, offset2];
    if (v2 == current_value && v1 == current_value + 1) return [offset2, offset1];
    return null;
}

function merge_chains(chain1:Array, chain2:Array):Array {
    var tmp:Array = [];
    for (var i:int = 0; i < chain1.length; i++) tmp.push(chain1[i]);
    tmp.push(chain2[1]);
    return tmp;
}

function print_field():void {
    for (var pos_y:int = 0; pos_y < N; pos_y++) {
        var offset:int = pos_y * N;
        var s:String = "";
        for (var pos_x:int = 0; pos_x < N; pos_x++) {
            var v:int = field[offset++];
            if (v == 0) s += "[0]"; else s += " " + v + " ";
        }
        trace(s);
    }
}

function print_chains(chain_list):void {
    var cl:int = chain_list.length;
    trace("\nchains found: " + cl);
    if (cl) trace("chain length: " + chain_list[0].length);
    for (var i:int = 0; i < cl; i++) {
        var chain:Array = chain_list[i];
        var s:String = "";
        for (var j:int = 0; j < chain.length; j++) s += chain[j] + ":" + field[chain[j]] + " ";
        trace(s);
    }
}

Sample output:

 1  2  1  3  2  2  3  2  4 
 4  3  1  2  2  2 [0][0] 1 
[0][0] 1  2  4 [0] 3  3  1 
[0][0] 5  4  1  1 [0][0] 1 
 2  2  3  4  3  2 [0] 1  5 
 4 [0] 3 [0] 3  1  4  3  1 
 1  2  2  3  5  3  3  3  2 
 3  4  2  1  2  4  4  4  5 
 4  2  1  2  2  3  4  5 [0]

chains found: 2
chain length: 5
23:0 32:1 41:2 40:3 39:4 
33:0 32:1 41:2 40:3 39:4 

回答4:

I implemented it in my own Lisp dialect, so the source code is not going to help you that much :-) ...

EDIT: Added a Python version too.

anyway the idea is:

• write a function paths(i, j) --> (maxlen, number) that returns maximal length of paths starting from (i, j) and how many of them are present..
• this function is recursive and looking at neighbors of (i, j) with value M[i][j]+1 will call paths(ni, nj) to get the result for valid neighbors
• if the maximal length for a neighbor is bigger than current maximal length you set a new current maximal length and reset the counter
• if the maximal length is the same as current then add the counter to the total
• if the maximal length is smaller just ignore that neighbor result
• cache the result of the computation for the cell (this is very important!). In my version the code is split in two mutually recursive functions: paths that checks the cache first and calls compute-paths otherwise; compute-paths calls paths when processing neighbors. The caching of a recursive call is roughly equivalent to an explicit Dynamic Programming approach, but sometimes easier to implement.

To compute the final result you basically do the same computation but adding up the result for all 0 cells instead of considering neighbors.

Note that the number of different paths can become huge, and that's why enumerating all of them is not a viable option and caching/DP is a must: for example for a N=20 matrix with values M[i][j] = i+j there are 35,345,263,800 maximal paths of length 38.

This algorithm is O(N^2) in time (each cell is visited at most once) and requires O(N^2) space for the cache and for the recursion. Of course you cannot expect to get anything better than this given that the input is composed of N^2 numbers itself and you need at least to read them to compute an answer.

(defun good-paths (matrix)
  (let** ((N (length matrix))
          (cache (make-array (list N N)))
          (#'compute-paths (i j)
            (let ((res (list 0 1))
                  (count (1+ (aref matrix i j))))
              (dolist ((ii jj) (list (list (1+ i) j) (list (1- i) j)
                                     (list i (1+ j)) (list i (1- j))))
                (when (and (< -1 ii N) (< -1 jj N)
                           (= (aref matrix ii jj) count))
                  (let (((maxlen num) (paths ii jj)))
                    (incf maxlen)
                    (cond
                      ((< (first res) maxlen)
                       (setf res (list maxlen num)))
                      ((= (first res) maxlen)
                       (incf (second res) num))))))
              res))
          (#'paths (i j)
            (first (or (aref cache i j)
                       (setf (aref cache i j)
                             (list (compute-paths i j))))))
          (res (list 0 0)))
    (dotimes (i N)
      (dotimes (j N)
        (when (= (aref matrix i j) 0)
          (let (((maxlen num) (paths i j)))
            (cond
              ((< (first res) maxlen)
               (setf res (list maxlen num)))
              ((= (first res) maxlen)
               (incf (second res) num)))))))
    res))

Edit

The following is a transliteration of the above in Python, that should be much easier to understand if you never saw Lisp before...

def good_paths(matrix):
    N = len(matrix)
    cache = [[None]*N for i in xrange(N)] # an NxN matrix of None

    def compute_paths(i, j):
        maxlen, num = 0, 1
        count = 1 + matrix[i][j]
        for (ii, jj) in ((i+1, j), (i-1, j), (i, j-1), (i, j+1)):
            if 0 <= ii < N and 0 <= jj < N and matrix[ii][jj] == count:
                nh_maxlen, nh_num = paths(ii, jj)
                nh_maxlen += 1
                if maxlen < nh_maxlen:
                    maxlen = nh_maxlen
                    num = nh_num
                elif maxlen == nh_maxlen:
                    num += nh_num
        return maxlen, num

    def paths(i, j):
        res = cache[i][j]
        if res is None:
            res = cache[i][j] = compute_paths(i, j)
        return res

    maxlen, num = 0, 0
    for i in xrange(N):
        for j in xrange(N):
            if matrix[i][j] == 0:
                c_maxlen, c_num = paths(i, j)
                if maxlen < c_maxlen:
                    maxlen = c_maxlen
                    num = c_num
                elif maxlen == c_maxlen:
                    num += c_num
    return maxlen, num