PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Turbo 版老鼠走迷宮..

看板Prob_Solve (計算數學 Problem Solving)作者yauhh (喲)時間12年前 (2012/11/06 23:59)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串3/4 (看更多)

※ 引述《yauhh (喲)》之銘言： : ※ 引述《EdisonX (閉上眼的魚)》之銘言： : : [2] 如何產生出一條迷宮 : : 如何產生一條，具有唯一解，且任兩點必相通的迷宮？ : : 假設是 M x N，網路上是有種方法可以產生，但前提限制是， : : M, N 必須為奇數 ( 為什麼一定要奇數我也想不透，但實際跑偶數真的有問題)， : : 請問是否有產生符合以下條件迷宮的方法？ : : (a) 出口 / 入口不用限制在邊界上，可以設在迷宮內部 : : (b) 任兩點必定相通 : : (c) M x N，M, N >2，For All M, N : : (d) 不會造成迴路，且只有唯一一條路徑。 : 我不會程式解迷宮,不過你這個問題,如何產生有惟一解的迷宮,從你的描述, : 大概知道答案了. : 樹結構,其中二點特性,一是任二點之間只存在一條連通路徑,二是不存在迴路. : 做一個任意樹,選一個端點做入口,另一個端點做出口,把樹攤開放在平面上, : 就是你要的迷宮. 我很雞婆,再延伸一下想法: 有個亂數取值函數寫成 rand(m..n) 表示產生介於 m, n (含二數)之間的整數. 從一個點(x,y)開始長出路線,由於視一面是退路,所以只亂數往其他三面長出路線. n1= (rand(0..1)==0? null : rand(0..u1)) (x,y)----------------------------------------->(x+n1,y) | n2= (rand(0..1)==0? null : rand(0..u2)) +----------------------------------------->(x,y+n2) | n3= (rand(0..1)==0? null : rand(0..u3)) +----------------------------------------->(x-n3,y) 然後三個點用相同的方法去長出各自的三條路,這樣長一長就會是一個迷宮的底子. 然後,每一條路長出去,前面應該會撞到另一條橫擋的路,此時就可以設計看要跨躍, 連接並中斷,或者在撞到之前停止生長. 長路到撞壁之前也可以調整看要連接並中斷或是在撞到之前停止. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.167.55.9