<分区>
基本上,你有这样的东西:
0 9 5 3'
4 1 5' 4'
5 7' 6' 9
2 8' 5 10
在这种情况下,最长的蛇将是 3 -> 4 -> 5 -> 6 -> 7 -> 8。我将 ' 放在数字后面以帮助直观地显示它。
您可以水平和垂直移动。矩阵可以是 n x m,因此实际上对行数和列数没有限制。
解决这个问题的最佳方法是什么?
我考虑过从位置 n/2 和 m/2 开始,然后递归地进行广度优先搜索并跟踪我能找到的最大间隔。我不确定如何最好地解决它。
标签 algorithm
<分区>
基本上,你有这样的东西:
0 9 5 3'
4 1 5' 4'
5 7' 6' 9
2 8' 5 10
在这种情况下,最长的蛇将是 3 -> 4 -> 5 -> 6 -> 7 -> 8。我将 ' 放在数字后面以帮助直观地显示它。
您可以水平和垂直移动。矩阵可以是 n x m,因此实际上对行数和列数没有限制。
解决这个问题的最佳方法是什么?
我考虑过从位置 n/2 和 m/2 开始,然后递归地进行广度优先搜索并跟踪我能找到的最大间隔。我不确定如何最好地解决它。
最佳答案
您可以创建一个图形,其中节点是矩阵位置,顶点指向从数字 N 到 N+1 的邻居。
构建图形后,您的问题就是找到该图形中最长的路径之一。
关于algorithm - 给定一个整数矩阵,找到递增 1 个数字的最长连续蛇,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29179404/