您好,我是堆栈溢出的新手。我需要帮助解决 Java 程序中的以下问题
我有一个二维数组,我需要找出可以从任何节点遍历的最大长度。如果它的值小于当前元素,我可以从一个元素遍历到连接的元素(左/右/上/下)。我需要在二维整数数组中找到上述条件可能的最大路径 下面是5*5的数组
7 2 3 4 5
36 37 38 34 6
33 44 46 40 7
24 43 42 41 8
35 32 47 30 9
上述数组中最长的路径是 46-44-43-42-41-30-9-8-7-6-5-4-3-2 共 14。
请帮助我编写 Java 代码。提前致谢
最佳答案
将数据表示为 graph ,其中 G=(V,E)
和 V={ all squares}
, E = { (u,v) | u is adjacent to v and u.value < v.value)
请注意,上图是一个 Directed Acyclic Graph(因为如果 (u,v) 在 E 中,则没有从 v
到 u
的路径,因为它需要一条路径 v->v1->v2->...->u
这样 v.value > v1.value > v2.value > .... > u.value
,但是 operator>
是可传递的,所以这意味着v.value > u.value
,而我们知道 v.value < u.value
- 因为 (u,v)
在 E
中,所以矛盾,这样的路径不存在。
在这个减少之后 - 你可以简单地解决 longest path in a DAG ,这是一个更简单的问题。
关于java - 在给定条件下查找二维数组中路径的最大长度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14673333/