Week3 - 挑戰題:走迷宮


Posted by rockyooooooo on 2021-04-20

看這題目感覺就是要用演算法了,果然提示就說了請搜尋關鍵字:BFS

BFS(Breadth-First Search),廣度優先搜尋

從 root 開始,先橫向搜尋所有鄰近節點,放到 queue (先進先出)裡,再依序從找到的鄰近節點,繼續找他的鄰近節點並放進 queue,直到找到目標,或所有節點都被找到。
(若同一層有節點未存取,會先存取同一層的節點)

再來就要思考,怎麼實作 BFS,也是最有挑戰性的部分。
策略:

  1. 從 root 開始(左上角)
  2. 判斷他的上下左右是否為目標(右下角),是的話成功走出迷宮,若非目標,則判斷是否可以通行,可以的話放進 queue
  3. 拿 queue 的第一個 node,重複步驟 2,直到找到目標(走到左下角)

寫出來才發現,這個策略有個致命的缺陷:
根本不知道路徑到底怎麼走的,只是一味地把整個地圖走過一次

後來在網路上查到這個討論

一開始看不太懂,一直覺得存路徑而非存位置很奇怪,而且一開始的 queue 是個三層的陣列,讓我腦袋一直打結
拿張白紙把所有的變數照著 code 一行一行執行,才懂了這樣寫的邏輯!

  1. queue裡存是一個一個可能的path(路徑),path存的是走過的position(位置)
  2. 每次的while迴圈會讓path往前走一步,也可能讓path往不同的方向前進而一分為二,甚至更多
  3. 短的path走完才會走長的path(queue 先進先出),所以最短path會先被找到

放上 LIOJ 後,出現 Time Limit Exceeded,只好再繼續研究怎麼樣比較快


抓到兇手了,迷宮 array 裡的每個元素都是 string,而我會把走過的位置改成*來表示,避免路徑重複
但 string 是 immutable 的
所以要先把 string 改成 array 存起來,就解決啦!
(果然只是 code 沒寫好,我就覺得怎麼可能慢到哪裡去!)










Related Posts

在 Windows 上測試 Safari

在 Windows 上測試 Safari

Day 160

Day 160

第一周筆記心得

第一周筆記心得


Comments