决策寻路
Pathfinding with decisions
考虑以下（有限）映射：
P░b▓░░░░G
░░░a░░░░░
░░░▓▓▓▓▓▓
░░░B░A░░░
░░░░░░░░░
其中 P 和 G 分别是玩家和目标。 a 和 b 是门，可以通过按下开关 A 和 B 打开（变成可行走的节点）。只能使用一个开关。 ░ 是可行走的节点，▓ 是墙。
您将如何解决这个问题？显然，简单的启发式 (A*) 不会执行，因为您必须决定使用哪个开关。我唯一的解决方案是暴力破解整个事情——递归地尝试每条路径和沿它的每个开关（只要之前没有使用过开关）。这行得通，但正如我之前提到的，它是蛮力，这意味着时间复杂度是巨大的。
问题是：另一种算法可以做得更好吗？如果是这样，它看起来怎么样？
（我试图搜索相关问题，但一无所获。抱歉，如果这可能是重复的。）
如果过程中只能使用一个开关，则可以解决O(W*H)中的问题。
从 P 位置的 BFS 开始，之后如果达到 G 那么你就完成了，否则对于每个门（k)-switch(K)你到达了，从k位置继续BFS（当然，你不能通过任何其他门）。
继续该过程，直到您到达 G 或处理完每个门。请注意，您必须只处理第一个DFS（从P开始）到达的门，而不是第一个DFS门，并且任何门 k 都可以在相应的 BFS 中行走，而不是在其他 BFS 期间行走。
由于所有位置最多访问一次，时间复杂度为O(W*H).
考虑以下（有限）映射：
P░b▓░░░░G
░░░a░░░░░
░░░▓▓▓▓▓▓
░░░B░A░░░
░░░░░░░░░
其中 P 和 G 分别是玩家和目标。 a 和 b 是门，可以通过按下开关 A 和 B 打开（变成可行走的节点）。只能使用一个开关。 ░ 是可行走的节点，▓ 是墙。
您将如何解决这个问题？显然，简单的启发式 (A*) 不会执行，因为您必须决定使用哪个开关。我唯一的解决方案是暴力破解整个事情——递归地尝试每条路径和沿它的每个开关（只要之前没有使用过开关）。这行得通，但正如我之前提到的，它是蛮力，这意味着时间复杂度是巨大的。
问题是：另一种算法可以做得更好吗？如果是这样，它看起来怎么样？
（我试图搜索相关问题，但一无所获。抱歉，如果这可能是重复的。）
如果过程中只能使用一个开关，则可以解决O(W*H)中的问题。
从 P 位置的 BFS 开始，之后如果达到 G 那么你就完成了，否则对于每个门（k)-switch(K)你到达了，从k位置继续BFS（当然，你不能通过任何其他门）。
继续该过程，直到您到达 G 或处理完每个门。请注意，您必须只处理第一个DFS（从P开始）到达的门，而不是第一个DFS门，并且任何门 k 都可以在相应的 BFS 中行走，而不是在其他 BFS 期间行走。
由于所有位置最多访问一次，时间复杂度为O(W*H).