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

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

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間12年前 (2012/11/07 07:30)推噓1(1推 0噓 0→)

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

https://gist.github.com/4028447 http://codepad.org/lNFPCSe6 輸入： w 寬 h 高 r 一開始幾個生長點趕著上班回頭在補內文。 Bleed ※ 引述《EdisonX (閉上眼的魚)》之銘言： : 老鼠走迷宮是老到不能再老的問題， : 有幾個題目是網路上看到的面試題目， : 但小弟卻沒想到解法，上網找了些資料， : 說明並不非常詳盡，於此請教各位先進意見。 : [0] 探討的迷宮 : 迷宮種類很多，這個不贅述，我想探討的主要只有一個特性， : 迷宮內的任意兩點一定可以相通。 : [1] 尋找最短路徑 : 假設一條迷宮不只一條唯一路徑，也有可能造成回路， : 給定入口與出口，請問怎麼找出最短路徑？ : [2] 如何產生出一條迷宮 : 如何產生一條，具有唯一解，且任兩點必相通的迷宮？ : 假設是 M x N，網路上是有種方法可以產生，但前提限制是， : M, N 必須為奇數 ( 為什麼一定要奇數我也想不透，但實際跑偶數真的有問題)， : 請問是否有產生符合以下條件迷宮的方法？ : (a) 出口 / 入口不用限制在邊界上，可以設在迷宮內部 : (b) 任兩點必定相通 : (c) M x N，M, N >2，For All M, N : (d) 不會造成迴路，且只有唯一一條路徑。 : 這種問法讓我感到很不好意思，但想了半天真的是沒什麼想法 = = : 唯一有「一點點」想法的是尋最短路徑，「似乎」可以用 DP 解？ : 效率分析和實作就一直卡死。 : 小弟承認演算法 / 資料結構沒 k 完，請問要解上面兩個問題， : 是否該再補足哪些部份？ : 可指點個概念，或給些 keyword ，小弟實作上若有問題再回來請教， : 謝謝各位先進不吝賜教，感激不盡。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.25.242.134