[問題] Turbo 版老鼠走迷宮..
看板Prob_Solve (計算數學 Problem Solving)作者EdisonX (閉上眼的魚)時間12年前 (2012/11/06 15:42)推噓2(2推 0噓 6→)留言8則, 5人參與討論串1/4 (看更多)
老鼠走迷宮是老到不能再老的問題，
有幾個題目是網路上看到的面試題目，
但小弟卻沒想到解法，上網找了些資料，
說明並不非常詳盡，於此請教各位先進意見。
[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: 180.177.76.161
※ 編輯: EdisonX 來自: 180.177.76.161 (11/06 15:48)
推
11/06 16:08, , 1F
11/06 16:08, 1F
推
11/06 16:36, , 2F
11/06 16:36, 2F
→
11/06 17:09, , 3F
11/06 17:09, 3F
→
11/06 19:10, , 4F
11/06 19:10, 4F
→
11/13 23:27, , 5F
11/13 23:27, 5F
→
11/13 23:30, , 6F
11/13 23:30, 6F
→
11/13 23:31, , 7F
11/13 23:31, 7F
→
11/14 01:34, , 8F
11/14 01:34, 8F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
