algorithm - 如何找到二维数组中最长的序列？

Question

给定一个二维网格，具有以下约束，我想找到最长的子序列:

1. 允许向上、向右、向左、向下、对角线移动
2. 当前值和下一个值之间的差应该大于或等于 3(即绝对差)。
3. 访问过的单元格不应重复
4. 网格最大为 10 x 10
5. 不允许在下面的例子中做 4 -> 9

例子:

824
061
379

上述输入的最长路径长度为8，顺序为9,1,6,2,8,0,7,3

我厌倦了使用多个 for 循环，但它的效率非常低。我想知道如何使用动态编程。任何帮助将不胜感激。

Answer 1

只需运行 bfs (Breadth-first search)通过遵循约束从网格中的每个可能的来源。例如，在您给定的示例输入中，可能的源数是 9。然后，将路径保存在一些合适的数据结构中。保存路径后，检查哪条路径最长，这就是您的答案。