C++有关王子拯救公主最短路径
本帖最后由 1248762042 于 2021-6-4 00:10 编辑在九宫格(行数列数可自定义)中 每个格子都有不同的随机数(可能为负数) 从最左上角到最右下角 一次只能向下或向右走 然后将所走路径上的数字相加 如何找到数字和最小的路径 https://leetcode-cn.com/problems/dungeon-game/ 力扣174题
你自己看看题解吧 我觉得可以试试用广度优先算法，从骑士出发的位置开始，寻找去往每一个点的最优解，例如，去往-10的最优解必定是-2，-3而非-2，-5。这样，-2-5-10的这条路径就可以排除掉。然后每个点基于之前的最优解继续寻找到达这个点的最优解。最终，当所有的点都找出来之后，肯定会有到达公主位置的最优解。我自己写了个小游戏，寻路的算法就是这样的。 对了，基于上述方法，计算机大概只需要对地图进行m*n次上述操作，就可以找到最优解了，也不会太花时间
页:
[1]