這份文章還沒到放碼或說明的地步 (沒放上來是 source 沒到自己滿意的地步),

主要記錄一些議題 ,有興趣的人可參考。

關於迷宮之定義,曾閱過一份文章 (憑印象,忘了出處,有誤請補充或指正) ,

給予之其中一個特性為,

任意兩點之路徑必須唯一且存在,

這裡所探討之議題必須把「唯一」限制拿掉才可繼續討論下去

 

 

 

(1) 從入口到出口,找出其中一條路徑 (考慮可能沒出口) 。1 題

(2) 從入口到出口,找出所有可能之路徑 (考慮可能沒出口) 。  1 題 

(3) 試著以 (1) 為例,將遞迴去除。 1 題

(4) 試著以 (1) 為例,輸出從入口到出口路徑 ( 只顯示成功的那條 )。 1 題

(5) 試著以 (1) 為例,輸出從入口,走到出口,之過程路徑 ( 走失敗做迴溯的動作也要顯示 )。 1 題

(6) 假設路徑至少 1 條以上,求出最短路徑 1 題

(7) 使用者輸入 N ,迷宮大小為 maze[N][N],最外圍全都為牆,使用者輸入起點( maze[1][y1] ) 與終點位置 (maze[N-2][y2] ), 試產生一迷宮1 題

 

 

1、2、4,網路上很多範例可參考,均以 DFS 為範本,

有興趣可以 BFS 方式完成,不贅述;

3 去遞迴  一般人可能較不想練習,無妨;

6 求最短路徑是某科技廠面試題 ( 這題筆者也還沒做出來 ) ;

 

7 迷宮產生演算法不少,要深入可以玩很久,筆者沒在這議題上圍繞。

目前資料可以找到最多的大概是奇數 N,keyword : 珊瑚樹。

能同時適用奇數/偶數 N 之迷宮產生器 ( 可不要求任兩點之路徑必唯一 ) 筆者沒再深入,

有經驗之網友歡迎提供相關經驗或資訊,先行感謝。

edisonx 發表在 痞客邦 PIXNET 留言(1) 人氣()


留言列表 (1)

發表留言
  • novus
  • 幾年前應知識+網友要求寫的產生和走迷宮範例(單一路徑、任意尺寸、非遞回DFS、Win32),我記得bug已經抓完了
    http://www.phpbbserver.com/graphicsparalle/viewtopic.php?t=265&mforum=graphicsparalle
    簡化自我更早之前寫的程式,之前那個版本會顯示所有嘗試過的路徑,不過程式碼已經丟了。

    不太相關的作品... 其實我寫過不少迷宮相關程式,不過我的重心幾乎都不在迷宮演算法本身,所以可以說對這個迷宮沒什麼研究。
    http://novus.pixnet.net/blog/post/26971425
    http://novus.pixnet.net/blog/post/20282812

    我做過最奇怪的迷宮產生器是用 Excel VBA 寫的,演算法會為每個格子填上數字(和背景同色所以是隱形的),而事先設定的自動樣式會根據數字為每個格子加上不同格線,於是就形成迷宮。

    最短路徑的想法:基本上只要能列舉所有路徑,最短路徑應該可用 Dijkstra 之類的演算法解決。(我沒試過就是了)
  • novus 提供了我好多資訊啊 !! 真是太感激了 !!
    魔幻迷宮那份看了眼睛真的很酸..

    [註] 看完 code 之後我開始懷疑自己不會寫程式 Orz

    edisonx 於 2012/10/15 01:03 回覆

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼