携程测试编程
发布于 2017-09-21 20:17 3234 次浏览 0 赞 来自 我要提问  

计算最长奔跑路径长度

时间限制:C/C++语言 3000MS;其他语言 5000MS
内存限制:C/C++语言 65536KB;其他语言 589824KB

题目描述:

Tom猫喜欢从高的地方往低的地方奔跑,现在通过矩阵的方式表示某一区域的高低,如下所示

1 2 3 4

12 13 14 5

11 16 15 6

10 9 8 7

可以从矩阵中的某一点奔跑到上下左右相邻的较小的点上。例如上面所示的矩阵中一条可以奔跑的路径为14-13-2-1,长度为4,而最长的路径显然是16-15-14-...-4-3-2-1,长度为16。

现在给出代表区域高低的矩阵,请你计算出最长的奔跑路径的长度。


3 条回复

写出来了吗?求分享

2017-09-21 20:29

这道题我只会用暴力的方式求解,对每个点都用广度优先搜索,找四邻域

2017-09-21 20:32
coder_EERKZNRJ 回复 coder_KUTBQ9GS

可以+记忆划搜索

2017-09-21 21:03
添加回复
回到顶部