作者yauhh (哟)
看板Prob_Solve
标题Re: [问题] Turbo 版老鼠走迷宫..
时间Tue Nov 6 20:27:45 2012
※ 引述《EdisonX (闭上眼的鱼)》之铭言：
: [2] 如何产生出一条迷宫
: 如何产生一条，具有唯一解，且任两点必相通的迷宫？
: 假设是 M x N，网路上是有种方法可以产生，但前提限制是，
: M, N 必须为奇数 ( 为什麽一定要奇数我也想不透，但实际跑偶数真的有问题)，
: 请问是否有产生符合以下条件迷宫的方法？
: (a) 出口 / 入口不用限制在边界上，可以设在迷宫内部
: (b) 任两点必定相通
: (c) M x N，M, N >2，For All M, N
: (d) 不会造成回路，且只有唯一一条路径。
我不会程式解迷宫,不过你这个问题,如何产生有惟一解的迷宫,从你的描述,
大概知道答案了.
树结构,其中二点特性,一是任二点之间只存在一条连通路径,二是不存在回路.
做一个任意树,选一个端点做入口,另一个端点做出口,把树摊开放在平面上,
就是你要的迷宫.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.167.55.9
1F：推 EdisonX:想了一下是很有道理没错,只是这样的 tree 似乎只能决定 11/06 20:51
2F：→ EdisonX:road, 有点想不透展开成二维作法. 但这概念真的很鲜. 11/06 20:52
3F：→ suhorng:上一篇的推文有提到 随便生个图然後找spanning tree 11/06 21:01
4F：→ yauhh:我想关键在找到一个适合的表达法表达迷宫,树是一种 11/06 21:10
5F：推 EdisonX:嗯，我 k 过书再回来聊好了, 谢谢楼上两位的回答 :) 11/06 23:28