给定一个整数矩阵，找到递增1的连续数字的最长连续蛇形长度。

Question

给定一个整数矩阵，找到递增1的连续数字的最长连续蛇形长度。

5

基本上，您有类似以下的内容：

在这种情况下，最长的蛇将是3 -> 4 -> 5 -> 6 -> 7 -> 8。我在数字后面加上 ' 来帮助可视化显示。

您可以横向和纵向移动。矩阵可以是n x m的，因此行数和列数没有真正的限制。

确定最佳方法是什么？

我考虑从位置n / 2和m / 2开始，然后递归地进行广度优先搜索，并跟踪我可以找到的最大间隔。我不确定最好如何解决它。

- David

考虑使用“diff（...）”命令获取矩阵中相邻两个数字的差值，并检查该差值是否为1。在Python中，例如，可以使用以下命令实现（http://docs.scipy.org/doc/numpy/reference/generated/numpy.diff.html）。 - Jesper - jtk.eth

1

我会从深度优先搜索开始 - 从起始节点向上和向下遍历 - 在这里，我会将每个访问过的节点从可以开始DFS的节点集合中删除（因为如果它被访问过，它必须已经是蛇的一部分）。 - user2864740

矩阵是给定的还是需要自己生成？ - Jesper - jtk.eth

假设它是随机生成的。 - David

这基本上是同一个问题，没有链接问题中从0开始的限制。这个限制并不是一个主要问题，链接线程很好地解释了应该如何处理它。(主要区别在于给DAG中的每个源都赋值0，而不仅仅是那些单元格值为0的源) - amit

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kuroi neko · Answer 1

你可以创建一个图，其中节点是矩阵位置，边缘从数字N指向N+1邻居。

一旦建立了图形，您的问题就相当于在此图形中查找最长路径之一。