Edison.X. Blog

 

這份文章還沒到放碼或說明的地步 (沒放上來是 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 之迷宮產生器 ( 可不要求任兩點之路徑必唯一 ) 筆者沒再深入，

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