从所有起点解决迷宫
Maze Solving From All Start Points
最近我遇到了一个问题;
假设一个具有字符 *、.、C 的迷宫。* 表示墙壁并且允许 ./C。只有一个点被标记为 C。现在给定一个机器人站在任何允许的点上，存在一系列命令（例如 LDDRU 或 LLLRRDU 等），这样如果机器人从任何允许的点开始，它就会通过C至少一次。
例如：
******
*.C..*
**.***
*....*
******
命令：RLLURUU
现在我知道如何使用 DFS/BFS（最短路径）解决迷宫问题了。但是任何人都可以提供有关如何处理此类问题的提示吗？
编辑：如果下一步是进入墙壁/迷宫外，它会被忽略。和往常一样 L 是左 R 是右 U 是上 D 是下。
此问题与有限自动机的synchronizing words或重置序列的概念有关。您可以想象构建一个自动机，其中
- 每开space，加上C，就是一个状态；
- 除了 C 之外的每个状态都会在每一次撞墙的移动中转换到自身；
- 如果在指定方向上有开放点，除 C 之外的每个状态都会转换到指定方向上的相邻开放状态；和
- C 状态在所有移动中都转换为自身。
鉴于此自动机，您现在正在寻找一个将每个状态都带到 C 状态的序列，从而连接到同步单词。有许多算法可以找到同步词，其中任何一个都可以用来解决这个特定的问题。一种选择是 build the power automaton from the original automaton 并寻找从开始状态到 C 状态的路径，这（我相信）最终成为讨论将虚拟机器人折叠在一起的评论的理论上最佳版本（因为它总会找到最佳路径。）
最近我遇到了一个问题;
假设一个具有字符 *、.、C 的迷宫。* 表示墙壁并且允许 ./C。只有一个点被标记为 C。现在给定一个机器人站在任何允许的点上，存在一系列命令（例如 LDDRU 或 LLLRRDU 等），这样如果机器人从任何允许的点开始，它就会通过C至少一次。
例如：
******
*.C..*
**.***
*....*
******
命令：RLLURUU
现在我知道如何使用 DFS/BFS（最短路径）解决迷宫问题了。但是任何人都可以提供有关如何处理此类问题的提示吗？
编辑：如果下一步是进入墙壁/迷宫外，它会被忽略。和往常一样 L 是左 R 是右 U 是上 D 是下。
此问题与有限自动机的synchronizing words或重置序列的概念有关。您可以想象构建一个自动机，其中
- 每开space，加上C，就是一个状态；
- 除了 C 之外的每个状态都会在每一次撞墙的移动中转换到自身；
- 如果在指定方向上有开放点，除 C 之外的每个状态都会转换到指定方向上的相邻开放状态；和
- C 状态在所有移动中都转换为自身。
鉴于此自动机，您现在正在寻找一个将每个状态都带到 C 状态的序列，从而连接到同步单词。有许多算法可以找到同步词，其中任何一个都可以用来解决这个特定的问题。一种选择是 build the power automaton from the original automaton 并寻找从开始状态到 C 状态的路径，这（我相信）最终成为讨论将虚拟机器人折叠在一起的评论的理论上最佳版本（因为它总会找到最佳路径。）