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