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

Question

基本上,你有这样的事情:

0 9 5 3'
4 1 5' 4'
5 7' 6' 9
2 8' 5 10

在这种情况下,最长的蛇将是3 - > 4 - > 5 - > 6 - > 7 - > 8.我把'数字放在这里以帮助在视觉上显示它.

你可以水平和垂直去.矩阵可以是nxm,因此行和列的数量没有实际限制.

想出这个的最佳方法是什么？

我想过从位置n/2和m/2开始,然后递归地进行广度优先搜索并跟踪我能找到的最大间隔.我不确定如何最好地解决它.

Answer 1

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

构建图表后，您的问题就是找到该图表中最长的路径之一。