最近我遇到一个问题:
假设一个迷宫有字符 *,.,C .* 代表墙壁，. >/C 是允许的。只有一个点被标记为C。现在，给定一个机器人站在任何允许的点上，存在一系列命令(例如LDDRU或LLLRRDU等)，这样如果机器人从任何允许的点，它至少通过 C 一次。
例如:
******
*.C..*
**.***
*....*
******
命令:RLLURUU
现在我知道如何使用 DFS/BFS 解决迷宫(最短路径)。但是任何人都可以提示我如何处理这样的问题吗？
编辑:如果下一步是进入墙壁/外部迷宫，则会被忽略。和往常一样 L 向左 R 向右 U 向上 D 向下。
最佳答案
这个问题与synchronizing words的概念有关。或有限自动机的重置序列。您可以想象构建一个自动机，其中
- 每个开放空间加上C，就是一个状态；
- 对于每次撞墙的 Action ，除 C 之外的每个状态都会转换为自身；
- 如果在指定方向上存在开路点，则除 C 之外的每个状态都会转换到该方向上的相邻开路状态；和
- C 状态在所有 Action 中都会转换到自身。
给定这个自动机，您现在正在寻找一个将每个状态带到 C 状态的序列，从而与同步单词建立联系。有多种算法用于查找同步词，其中任何一种都可以用来解决这个特定问题。一种选择是 build the power automaton from the original automaton并寻找从起始状态到 C 状态的路径，(我相信)最终成为谈论将虚拟机器人折叠在一起的评论的理论上最佳版本(因为它总是会找到最佳路径。)
关于algorithm - 从所有起点解决迷宫，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38558933/