从所有起点解决迷宫

最近我遇到了一个问题，说：
假定迷宫具有字符*,.,C。 *代表墙壁，./C被允许。只有一个点标记为C。现在给定一个僵尸站在任何允许点上，存在一系列命令（例如LDDRU或LLLRRDU等），使得如果僵尸程序从任何允许点开始，它至少通过C一次。
如：从所有起点解决迷宫

****** 
*.C..* 
**.*** 
*....* 
******

命令：RLLURUU

现在我知道如何解决使用DFS/BFS迷宫（最短路径）。但任何人都可以提供一个关于如何处理这样的问题的暗示吗？
编辑：如果下一步是进入墙壁/外部迷宫，它将被忽略。和往常一样L是左R是正确U IS UP D是关闭。

来源

2016-07-25 yobro97

最远可以水平移动3步;例如; LLL，你只能在网格中的三个位置;在接下来的R之后，你可以在垂直走廊的三个位置;在UU之后，你肯定已经通过了C，所以一般来说：做出一些减少你可能位置的数量的动作，然后跟踪你所有可能的机器人，并使每个动作通过C，通过使用“如果有墙，机器人不动”的规则。每当两个可能的机器人结束在同一个方格中时，移除其中一个。 – m69

@ m69，谢谢你的回答。但更清楚的是，你可以使用给出的例子，并解释你的逻辑到达答案....谢谢！ – yobro97

3行中有9个可能的位置;在LLL之后，任何机器人将位于其最左边的位置，所以现在只有3个可能的位置;在另一个R之后，这3个机器人将位于第二左边位置（垂直走廊）;在UU之后，它们都会在C上结束。 – m69

此问题与有限自动机的synchronizing words或复位序列的概念有关。你可以想象构建一个自动机，其中

每个开放空间加上C是一个状态;
除C以外的每个状态都会转换到其自身，以确定每次碰到墙壁的移动;
除C之外的每个状态在所指示的方向上转换到相邻的打开状态，如果在该方向上存在开放点;和
C状态在所有动作中转变为自己。

鉴于这个自动机，你现在正在寻找一个序列，每一个状态到C状态，因此连接到同步单词。有许多用于查找同步字的算法，并且它们中的任何一个都可以适用于解决这个特定问题。一种选择是build the power automaton from the original automaton并寻找从开始状态到C状态的路径，我相信这最终会成为关于将虚拟机器人合拢在一起的评论的理论最优版本（因为它总是会找到最佳路径）

来源

2016-07-25 03:31:17 templatetypedef

“构建功率自动机” - 即使我们只构建可访问的节点，它也是指数型的。更快吗？我甚至不需要最短的同步字。 –

您链接到维基百科的移动版本。请修复。 –

@JanDvorak哦，对不起，我没有意识到你不需要最短的解决方案。功率自动机的构造对于任意自动机来说是最坏情况指数，但我不确定这个机器人中的特定自动机是否会实际触发它。我将不得不考虑那一个。还有其他的方法是已知的最坏情况下的多项式时间，尽管我不太熟悉它们。 – templatetypedef

从所有起点解决迷宫

回答

相关问题