這份文章還沒到放碼或說明的地步 (沒放上來是 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 發表在 痞客邦 留言(1) 人氣()