具有约束、BFS 或 DFS 的最短路径算法

Question

问题陈述如下:

Given a map which has some obstacles in it. Given a starting point S and ending point E, find the shortest path from S to E. Note you can choose any(4) direction from S, but during the process, you can only go straight from the previous direction, unless you hit an obstacle.

我对这个约束很迷惑，但是在这个过程中，你只能

go straight from the previous direction, unless you hit an obstacle.

这是否意味着简单的 BFS 无法解决这个问题？修改后的 BFS 或 DFS 是否能够为此找到解决方案？

声明:我正在寻找解决方案，只是一些提示或想法。

Answer 1

是的，一个简单的 BFS 可以在任何单元格处转弯，而在这个问题中，你只能在撞墙时转弯。

问题仍然可以通过修改图上的 BFS 来解决。为了正确地模拟约束，您可以创建辅助顶点，从这些顶点您只能在一个方向上移动。

或者，您可以构建另一个具有加权边的新图，并在其上使用更通用的最短路径算法(Dijkstra 或 Ford-Bellman)。具体来说，当您站在一个单元格中并选择一个方向时，为您可以再次改变方向的单元格画一条边。该边的权重恰好是两个单元格之间直线路径的长度。