Week3 - 挑戰題：走迷宮

看這題目感覺就是要用演算法了，果然提示就說了請搜尋關鍵字：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 沒寫好，我就覺得怎麼可能慢到哪裡去！）