求指点：逃生路径的查找算法~~~

wjlkoorey258

一个迷宫是由N(无限制，你可以取任何值，比如20,50,90,1000等)多个房间组成，每两个房间之间有一条通道。这个通道有个神奇的特性，那就是当一个人从一个房间经过某条通道进入到另一个房间后，他身后那条通道会立即消失，同时其他三个方向上可能会出现新的通道，当然也可能没有新通道出现，那就证明这是个死胡同，走不通，但此时你已经退不回去了，说的粗俗点就是“你挂了”。

现在让你编一个程序，在一个给定的迷宫里面找到所有潜在可能的逃生路径，并将他们打印出来。注意：有可能会有环路哦！
要求：
        1、程序尽可能简练，算法的时间和空间复杂度没有强制要求，但要合情理。假如，你的程序处理1000个房间时，用了20多秒，那肯定是不合格的。
        2、将所有逃生路径全部输出，但不要重复输出相同的路径。
        3、程序必须能够正确处理可能存在的环路情况。

例如：

这个示例中有环路，编号为0的房间为出口处。
如果从房间号为127的格子出发，那么存在两条逃生路径。因此，你的程序应该输出像下面这样的结果：
starting in room 127
path found
in 127 go south
in 17 go south
in 8 go south
in 12 go west
in 25 go west
outside
path found
in 127 go south
in 17 go west
in 93 go south
in 25 go west
outside

tangboyun

和遍历目录树没啥大区别，刨除环路处理的话和普通的深度优先搜索没有差别。

迷宫的总的房间数确定的话，比如为N，那么深度优先搜索的深度也就确定了，不求最快速度的话，可以迭代kN次，还未终止的话，那可以确定是进入环路了，而且肯定运行了至少k个周期，求出这个周期。
好一些的设计可以在进入新节点时新建个hash表，簿记遍历过的所有节点，以此来推断是否进入环路。

noword2k

A+算法

shang2010

在研究中，mark