找好路径的最大长度在网格 [英] Find maximum length of good path in a grid

问题描述

由于是A N * N grid.Now我们需要找出最大长度，哪里好路径被定义为如下的一个很好的路径：

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. 在良好的路径总是从标记为0
系统单元启动
2. 我们只被允许移动向左，向右，向上或向下
3. 如果第i个单元格的值是说A，然后在该路径下一个单元格的值必须是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.

例：设N = 3，我们有3 * 3的矩阵如下：

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

0 3 2               
3 0 1               
2 1 0            

然后最大不错的路径长度在这里为3，这样的好路径的数量为4。

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

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

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

推荐答案

这个问题是一个变化最长路径问题，但是你的限制，使这个问题变得更加容易，因为这个图实际上是向无环图（ DAG）的，因而问题是solveable有效

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.

定义有向图 G =（V，E）如下：

• V = {所有单元矩阵} （完整性检查：| V | = N ^ 2）
• E = {（U，V）| u是毗邻V和值（U）+ 1 =值（V）}

• 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) }

请注意，从上面的定义所产生的图是一个DAG，因为你不能有任何的周期，因为这将导致有一些边缘 E =（U，V）这样值（U）＆GT;值（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).

现在，你只需要找到一个DAG 最长路径从任何起点。通过拓扑排序在图形上使用动态规划做到这一点，然后：

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) }

当您完成后，找到节点 v 与最大值 D（V），这是长最长的好路了。
发现本身是由再轧以上，追溯你的步骤背面的最大D（V），直至到达回初始节点值为0所做的路径。

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.

这种方法的复杂性是 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

以上会发现你对每个节点 v 好路数 D（V）的达到它。所有你现在要做的，就是找到了最大值 X 有一笔节点 v ，使得价值（V）= X 和 D（V）＆GT;在到达与所有节点值的路径0 ，总结的第（v）：

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

注意： （1） - 常规之类的作品在这里，但需要为O（n ^ 2logn）时间，以及拓扑排序需要O（N ^ 2）时间
（2）提示，（U，V）是一个边缘，如果：（1） U 和 v 相邻（2）值（U）+ 1 =值（v）的

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)

这篇关于找好路径的最大长度在网格的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！