小公司lucid software OA

小公司Lucid Software。我在career fair上投的他们,他们当场有一个coding challenge要求八分钟做完longest continuous sequence这道题,我跪了。。。不过后来还是发了HackerRank的OA,题目是这样的:给一个nm矩阵,要求找出符合要求的最长的从任意点出发,到任意点结束的路径。要求是可以走八个方向(上下左右和对角线),且下一个数与当前数的差的绝对值大于3。数据范围是n,m<=10。给七天做完。我觉得这题本质上是图上的最长路径的问题,是个NP hard问题,也就是搜索题,复杂度肯定是指数增长,只能通过剪枝来提高算法效率。我减到最后也只能通过一个68的矩阵,也就是差不多一半的最大数据量,然后就提交了。

想看楼主你怎么优化的,可不可以贴解题方法

请问lz有后续嘛?

前两天刚收到后续,没说结果,只是说抱歉久等了,我们最近太忙,但是你还得多等等。

lz 请问你是根据什么剪枝的啊 多谢

刚做完,用的backtrack 感觉复杂度有点太高了,虽然testcase全部能过但是感觉不太好 不知道楼主有什么好的剪枝算法可以交流一下吗?

请问层主就是加 visiting记录一个pos是否在dfs正在访问的路径上吗?我也是这么做的,但是test case5一直不过,不知道问题出在哪里

就是每一个独立的点一个独立的visiting 然后访问的时候dfs + backtrack 没发现有什么特殊的case过不了

谢谢,我已经做出来了!

我也是第五个过不了,请问是为啥啊