[已解决]C++有关王子拯救公主最短路径

1248762042 · 发表于 2021-6-3 21:33:54

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 1248762042 于 2021-6-4 00:10 编辑

Screenshot_2021-03-02-09-31-10-621_com.tencent.wemeet.app.jpg

Screenshot_2021-03-02-09-29-44-868_com.tencent.wemeet.app.jpg

在九宫格(行数列数可自定义)中每个格子都有不同的随机数(可能为负数) 从最左上角到最右下角一次只能向下或向右走然后将所走路径上的数字相加如何找到数字和最小的路径

最佳答案

月排行榜 / 总排行榜

lei1996

2021-6-4 09:15:28

https://leetcode-cn.com/problems/dungeon-game/ 力扣174题
你自己看看题解吧

跳转到最佳答案楼层

lei1996 · 发表于 2021-6-4 09:15:28

这个最佳答案由 lei1996 给出，感谢 lei1996 的回答。

单击隐藏图章

https://leetcode-cn.com/problems/dungeon-game/ 力扣174题
你自己看看题解吧

Henry6598 · 发表于 2021-6-4 13:30:48

我觉得可以试试用广度优先算法，从骑士出发的位置开始，寻找去往每一个点的最优解，例如，去往-10的最优解必定是-2，-3而非-2，-5。这样，-2-5-10的这条路径就可以排除掉。然后每个点基于之前的最优解继续寻找到达这个点的最优解。最终，当所有的点都找出来之后，肯定会有到达公主位置的最优解。我自己写了个小游戏，寻路的算法就是这样的。

Henry6598 · 发表于 2021-6-4 13:33:37

对了，基于上述方法，计算机大概只需要对地图进行m*n次上述操作，就可以找到最优解了，也不会太花时间

账号		自动登录	找回密码
密码			立即注册