迷失健康的迷宫中的最短路径 [英] Shortest path in a maze with health loss

问题描述

假设您有一个由2D矩阵表示的地牢。您有一个起点S（x1，y1）和一个终点E（x2，y2）。在此过程中，某些细胞中有一个数字，该数字会减去您的健康评分。其他单元格是您无法克服的障碍。您从5个健康点开始，并且需要找到从S到E的最短路径，这样您就不会死。

Suppose you have a dungeon, represented by a 2D matrix. You have a start point S (x1,y1) and an end point E (x2, y2). Along the way, some cells have a number in them, which subtract from your health score. Other cells are obstacles that you can't go through. You start with 5 health points, and you need to find the shortest path from S to E where you don't die on the way.

我知道使用了Dijikstra找到最短的路径。但是在这种情况下，最短的路径可能是您一路死去的路径。您如何找到不死的最短路径？请注意，只要您还活着到最后，就可以获得更多健康点来完成比赛。

I know that Dijikstra is used to find shortest paths. But in this case the shortest path might be one in which you die along the way. How do you find the shortest path where you don't die? Note that there is no advantage to completing the race with more health points so long as you're alive at the end.

推荐答案

解决此类问题的标准方法有时称为图形分层。您制作了5张原始图形的副本（在这种情况下，编号为0到4），其中到达图形 n 中的文本 v 意味着获取原始图形中的相应顶点在遭受 n 次死亡之后的图形。

The standard approach to problems like this is sometimes called 'graph layering'. You make 5 copies of the original graph (numbered 0 through 4 in this case), where getting to a vertext v in graph n means getting to the corresponding vertex in the original graph after suffering n deaths.

如果原始图形中的一条边使您丧命，那么它将连接每个图形中的一个顶点 i 到图 i + 1 中的顶点，否则它将连接图的相同版本中的顶点，就像原始图一样。

If an edge in the original graph costs you a life, then it connects a vertex in each graph i to a vertex in graph i+1, and otherwise it connects vertices in the same version of the graph just like the original.

构造完此图后，使用Dijkstra算法在任何层中找到到终端顶点的最短路径。

After constructing this graph, use Dijkstra's algorithm to find the shortest path to the terminal vertex in any layer.

这篇关于迷失健康的迷宫中的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！