mou*_*sey 6 c c++ algorithm data-structures
将大鼠置于迷宫中某个未知位置的迷宫中.
我们所能做的就是向上,向下,向右或向左的方向.我们有两种方法:
我们必须编写一个函数探索,如果我们找到出路则返回true,如果没有办法则返回false.
这是一个简单的图形问题,可以使用bfs或dfs算法解决,如果我们可以找到这些地方的标记.如果我们不能标记这些地方,我们可以循环访问相同的地方.如果没有标记,有人可以帮助我让老鼠走出迷宫吗？可能吗？
Mar*_*ers 11
广度优先和深度优先搜索都需要内存,而朴素算法可以无限循环.老鼠可能只有O(1)记忆.
解决它而不记住你去过的地方的一种方法是随机选择一个方向.解决时间将非常长,但最终应达到每个可达到的方格.这与2D随机游走有关.
令人惊讶的是,已经证明,在二维点阵上,当步数接近无穷大时,随机游走具有到达任何点(包括起点)的统一概率.