Re: [问题] Turbo 版老鼠走迷宫..

楼主: yauhh (小y宝贝)   2012-11-06 20:27:45
※ 引述《EdisonX (闭上眼的鱼)》之铭言:
: [2] 如何产生出一条迷宫
: 如何产生一条,具有唯一解,且任两点必相通的迷宫?
: 假设是 M x N,网络上是有种方法可以产生,但前提限制是,
: M, N 必须为奇数 ( 为什么一定要奇数我也想不透,但实际跑偶数真的有问题),
: 请问是否有产生符合以下条件迷宫的方法?
: (a) 出口 / 入口不用限制在边界上,可以设在迷宫内部
: (b) 任两点必定相通
: (c) M x N,M, N >2,For All M, N
: (d) 不会造成回路,且只有唯一一条路径。
我不会程式解迷宫,不过你这个问题,如何产生有惟一解的迷宫,从你的描述,
大概知道答案了.
树结构,其中二点特性,一是任二点之间只存在一条连通路径,二是不存在回路.
做一个任意树,选一个端点做入口,另一个端点做出口,把树摊开放在平面上,
就是你要的迷宫.
作者: EdisonX (卡卡兽)   2011-01-06 20:51:00
想了一下是很有道理没错,只是这样的 tree 似乎只能决定road, 有点想不透展开成二维作法. 但这概念真的很鲜.
作者: suhorng ( )   2011-01-06 21:01:00
上一篇的推文有提到 随便生个图然后找spanning tree
楼主: yauhh (小y宝贝)   2011-01-06 21:10:00
我想关键在找到一个适合的表达法表达迷宫,树是一种
作者: EdisonX (卡卡兽)   2011-01-06 23:28:00
嗯,我 k 过书再回来聊好了, 谢谢楼上两位的回答 :)

Links booklink

Contact Us: admin [ a t ] ucptt.com