veterinary 发表于 2013-8-11 07:57:15

求个遍历思路

某个迷宫，每隔一段时间随机生成一个固定路径。

比如，不同时间随机生成的路径如下：

1、s;s;s;w;w;s;s;s;s;s;e
2、s;s;s;w;s;s;s;w;s;s;e
3、s;s;s;s;e;e;s;s;w;s;s;e
4、s;s;s;s;s;s;w;w;s;s;e
5、s;s;s;s;s;s;s;s;e
6、s;s;w;s;s;e;s;w;s;s;s;e


总是往south方向走，总共有8个south（如同下地下城，有8层，尽管路口多，但不管怎么样，最后往下的方向就是8个）。
正确的路径中是不会出现往north走的（尽管有north的出口）。

这种是不是要所谓的深度遍历？求高人来点思路

北大侠客行MUD，中国最好的MUD

dmy 发表于 2013-8-11 08:15:36

如果无法判断下一出口是否是正确出口，就需要采用遍历。
由于需测到每个分叉的最深处才能判断是否是正确路径，所以需要深度遍历。
你这里有特别条件“最终路径没有N出口”，在深度遍历的基础上可以优先排除N出口的路径，以提高效率（下一步未访问点为N时直接返回，不需遍历该分支）。

poshu 发表于 2013-8-11 08:19:41

random出口遇到8口就往S到目的了？

veterinary 发表于 2013-8-11 08:29:19

有没有深度遍历的例子？？



如果无法判断下一出口是否是正确出口，就需要采用遍历。
由于需测到每个分叉的最深处才能判断是否是正确路 ...
dmy 发表于 2013-8-11 12:15 AM http://pkuxkx.com/forum/images/common/back.gif

veterinary 发表于 2013-8-11 08:30:37

有时会出现唯一的出口。。。死胡同




random出口遇到8口就往S到目的了？
poshu 发表于 2013-8-11 12:19 AM http://pkuxkx.com/forum/images/common/back.gif

bluse 发表于 2013-8-11 08:40:57

最深处 ...

poshu 发表于 2013-8-11 11:59:01

回复 5# veterinary


    这个简单啊
1个出口直接返回 继续random

poshu 发表于 2013-8-11 12:17:55

论坛搜索 mush 推车 教学
huacuoh 发表于 2013-8-11 12:14 PM http://pkuxkx.com/forum/images/common/back.gif


    二毛 还债
页: [1]
查看完整版本: 求个遍历思路