1

嗨，我是堆栈溢出的新手。我需要帮助来解决 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 代码。在此先感谢

4

1 回答 1

1

将数据表示为图形, 其中G=(V,E)和V={ all squares},E = { (u,v) | u is adjacent to v and u.value < v.value)

请注意，上面的图是一个有向无环图（因为如果 (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，所以是矛盾的，这样的路径是不可能存在的）。

在此减少之后 - 您可以简单地解决DAG 中的最长路径，这是一个更简单的问题。

于 2013-02-03T14:16:02.490 回答