c++ - 迷宫最少转弯

Question

我有一个我无法解决的问题。我有一个迷宫，我必须找到一条从点 S 到点 E 的路径，该路径的转弯最少。已知点 E 是可以到达的。我只能在 4 个方向上移动，左、右、上和下。它不一定是最短的路径，只要转弯最少即可。

我尝试将转弯数存储在优先队列中。例如，当我到达迷宫中的某个位置时，我会将转弯数添加到那里。从那里我会将他的邻居添加到优先队列中，如果它们还没有被访问过或者它们不是墙，具有我所坐的当前 block 的值，例如 t + x 可以具有以下值(0-如果邻居面向我所面对的相同方向当我靠近他时，如果方向不同则为 1)。似乎这种方法不适用于所有情况。

如果有人可以在没有任何代码的情况下向我提供一些提示，我将不胜感激。

Answer 1

您走在正确的轨道上。你需要为这个问题实现的是 Dijkstra's algorithm .您只需要考虑的不仅仅是点作为图形顶点，而是一对 (point,direction)。从每个顶点 (p,d) 你有 5 条边(尽管最后一条边可以被墙挡住):(p,0), (p,1 ), (p,2), (p,3), (p 在方向 d, d 上的邻居)。前四个边的权重为 1(当你在这里转弯时)，最后一个边的权重为 0(不转弯，只是向前移动)。算法足以忽略循环，并且对于权重为 0 的边也能很好地工作。当从优先级队列中提取任何顶点 (end point, _) 时，您应该结束。

此方法有一个问题，因为在此过程中检查了太多顶点。如果您的迷宫很小，那不是问题。否则，考虑一个称为 A* 的小修改。 .您需要一个好的启发式函数，描述目标转弯次数的下限。