c – 让老鼠走出迷宫

发布时间：2020-12-16 05:27:16 所属栏目：百科来源：网络整理

导读：将大鼠置于迷宫中某个未知位置的迷宫中. 我们所能做的就是向上,向下,向右或向左的方向.我们有两种方法： tryMove( direction)如果有墙则返回false,如果我们可以移动则返回true. bool hasLadder()：如果有一个要转义的梯子,则返回true. 我们必须编写一个函数

将大鼠置于迷宫中某个未知位置的迷宫中.

我们所能做的就是向上,向下,向右或向左的方向.我们有两种方法：

> tryMove(< direction>)如果有墙则返回false,如果我们可以移动则返回true.
> bool hasLadder()：如果有一个要转义的梯子,则返回true.

我们必须编写一个函数探索,如果我们找到出路则返回true,如果没有办法则返回false.

这是一个简单的图形问题,可以使用bfs或dfs算法解决,如果我们可以找到这些地方的标记.如果我们不能标记这些地方,我们可以循环访问相同的地方.如果没有标记,有人可以帮助我让老鼠走出迷宫吗？可能吗？

解决方法

广度优先和深度优先搜索都需要内存,而朴素算法可以无限循环.老鼠可能只有O(1)记忆.

解决它而不记住你去过的地方的一种方法是随机选择一个方向.解决时间将非常长,但最终应达到每个可达到的方格.这与2D random步行有关.

Amazingly,it has been proven that on a two-dimensional lattice,a random walk has unity probability of reaching any point (including the starting point) as the number of steps approaches infinity.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!