java - 在给定条件下查找二维数组中路径的最大长度

Question

您好，我是堆栈溢出的新手。我需要帮助解决 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 代码。提前致谢

Answer 1

将数据表示为 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 ，这是一个更简单的问题。