一个老鼠被放置在迷宫中的某个未知位置。
我们只能向上、下、左或右方向移动。我们有两种方法：
我们必须编写一个函数explore，如果找到出路则返回true，否则返回false。
这是一个简单的图形问题，如果我们能标记这些位置，就可以使用bfs或dfs算法来解决。如果我们无法标记这些位置，我们可以在循环中移动，重复访问相同的位置。如果迷宫没有标记，有人能帮我把老鼠从迷宫中带出来吗？这可能吗？
广度优先搜索和深度优先搜索都需要内存，而且一个简单的算法可能会无限循环。老鼠可能只有O(1)的内存。
一种不需要记忆已经到达过的位置的解决方法是随机选择一个方向。虽然解决时间会非常长，但最终应该能够到达每个可到达的方格。这与2D随机行走有关。
令人惊讶的是，在二维晶格上，当步数趋近于无穷大时，随机行走到达任何点（包括起点）的概率是1。
BFS
while (!Q.empty()){
v = Q.top()
neighbours = get_adj_list(v)
foreach (w in neighbours){
if (isWall(w) || isOutsideMaze(w)) skip
if (isTerminal(w)) printPathAndExit
if (dist[v] + 1 < dist[w])
dist[w] = dist[v] + 1
Q.push(w)
}
}
GEN_NEIGHBOURS
dx = {-1,1}
dy = {-1,1}
get_adj_list(v)
adj_list = []
for (i in dx)
for (j in dy)
adj_list << node(v.x-i,v.y-j)
return adj_list
编辑：现在我读到内存限制是O(1)。所以我猜你应该遵循旧方法，总是向右转，最终你会走出迷宫或回到起点。
编辑2：来自玉米迷宫提示：
与任何迷宫一样，如果始终向左或向右转，最终你会找到出路。沿着迷宫墙壁走而不抬起手指将使你保持正确的方向。
while( 1 )
{
if( search( MOVE_LEFT, i ) ||
search( MOVE_UP, i ) ||
search( MOVE_RIGHT, i ) ||
search( MOVE_DOWN, i ) )
{
return TRUE;
}
i++;
}
/* recursive function */
bool search( move_type move, long int length )
{
doMove( move ); /* actually move the rat to requested place */
if( hasLadder() )
return TRUE;
if( 0 == length )
return FALSE;
switch( move ) /* check each and return rat to previous place */
{
case MOVE_LEFT:
if( tryMove( MOVE_LEFT ) && search( MOVE_LEFT, length - 1 ) ) return TRUE;
if( tryMove( MOVE_UP ) && search( MOVE_UP, length - 1 ) ) return TRUE;
if( tryMove( MOVE_DOWN ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;
doMove( MOVE_RIGHT ); break;
case MOVE_UP:
if( tryMove( MOVE_LEFT ) && search( MOVE_LEFT, length - 1 ) ) return TRUE;
if( tryMove( MOVE_UP ) && search( MOVE_UP, length - 1 ) ) return TRUE;
if( tryMove( MOVE_RIGHT ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;
doMove( MOVE_DOWN ); break;
case MOVE_RIGHT:
if( tryMove( MOVE_UP ) && search( MOVE_UP, length - 1 ) ) return TRUE;
if( tryMove( MOVE_RIGHT ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;
if( tryMove( MOVE_DOWN ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;
doMove( MOVE_LEFT ); break;
case MOVE_DOWN:
if( tryMove( MOVE_LEFT ) && search( MOVE_LEFT, length - 1 ) ) return TRUE;
if( tryMove( MOVE_RIGHT ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;
if( tryMove( MOVE_DOWN ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;
doMove( MOVE_UP ); break;
}
return FALSE;
} /* search() */
这是一个经典问题，通常用作家庭作业。
试试这个：
...
正如马克注释的那样，我试图引导你了解的算法的最简版本可能会陷入循环。你该如何解决这个问题？
有趣的是@mousey会问一个关于老鼠的问题...无论如何。
我已经看到这个问题多次出现了。
第一种（天真的）解决方案是沿着左（或右）墙走，然而可能制作特定的迷宫，使老鼠最终跑在圈子里。
事实上，对于我尝试过的每一个确定性移动顺序（如2L、1R、2L、1R等），我们都可以想出一个会让老鼠在圈子里跑的迷宫。当然，循环越复杂，迷宫就越复杂。
因此，如果你有O(1)的内存，唯一的走出迷宫的方法似乎是随机行走，正如Mark Byers所提出的。不幸的是，你不能证明这样的算法无法走出迷宫。
另一方面，如果您具有O（N）的内存，那就归结为创建一个映射（不知何故）。我当时想到的策略是在我经过的每个位置上留下信息素（递增计数器），并且在移动时，在最少被访问的位置中进行选择。但是总是可以找到出路，所以我从来没有考虑过终止条件的情况。