[計程] 單班期中考的第二題的參考程式碼

[LoganChien (簡子翔)]

這二個晚上被計程期中考的第二題搞的心神不定，因為我覺得第二
題我應該有能力寫出來，可是沒有寫出來。所以今晚我花了一些時
間寫第二題。我用了三種方法來寫︰














(按 PAGE DOWN 繼續)

法一

DFS 去搜，不過如果沒有小心的去 Cut 就等著 TLE 吧！我考試的
時候就是用這一個方法，只能拿 6/10。所以如果要用這一個方法
你必需要有一個夠強的修剪搜尋樹的方法。

進一步提示：想一下若走到已經走過的格子，我們要如何決定要不
要繼續暴。


法二

用 BFS 去搜，不過也不一定可以拿滿分(我不確定有沒有陰險測資)，
你還是要試過所有的組合才可以找到最小的，所以你也會用到 Cut，
不然也是會 TLE。

陰險測資：

10000
10 5
ooooosssss
ssssowwwws
ssssosssws
ssssooosfs
ssssssooos


法三

用 BFS + Priority Queue 去搜尋，因為 Priority Queue 保證在佇
列前端第一個就一定是最短的候選解，所以只要找到 f 就會是答案。


法四

聽說助教可以用 迴圈 (不是遞迴、BFS) 寫出來，不過我想不出來。
有興趣者請洽助教。


-----

參考程式碼

聽說助教會公佈參考程式碼，所以我公佈我寫的應該沒有關係吧 (汗)，
下載網址如下：

(失效 X) http://www.csie.ntu.edu.tw/~b97073/midterm2-refcode.zip



感想

我覺得這一題出得還算不錯，可以讓大家練練遞迴、修剪、讓大家
去弄很奇怪的解法(BFS+Priority Queue)。

還有期中考的題目可以在 TestGirl 找到，考試時沒有寫出來的，
可以再去練習。

http://palcourse.csie.ntu.edu.tw/testgirl



















(請按 PAGE UP 繼續)


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.241.166
推 dennis2030:專業文!  不過可以請問BFS跟DFS是什麼嗎? 看不懂Q口Q
→ dennis2030:是某種演算法嗎?
推 averangeall:如果有修離散的人 就會知道XDDD
→ LoganChien:DFS 就是每到某一格，我們會先試四周的某一格，再看剛
→ LoganChien:再看剛才選的那一格的四周。直到走投無路才會回頭試下
→ LoganChien:一個方向的格子。
→ LoganChien:BFS 就是把第一格四周的格子列入清單，然後從清單最上
→ LoganChien:面的找下一個，下一個四周又會被加到清單底端。
推 sa072686:提BFS+Priority Queue太艱深了吧…
※ 編輯: LoganChien      來自: 140.112.241.166      (11/07 03:43)
→ anfranion:DFS = Depth First Search 深度優先搜尋
→ anfranion:BFS = Breadth First Search 廣度優先搜尋
→ anfranion:不過這...好像不適合這麼早就提這些吼囧a
→ anfranion:這是兩種演算法沒錯～離散只是有提到而已
推 iForests:其實只是求 (1,1) 到某一格 f 的最短路徑
推 iForests:並沒有你說的那麼難。
→ chenaren:超難 >.<
推 godgunman:有個關鍵是, 一個點的分支很小, 頂多三方向 (不會回頭)
→ godgunman:所以直接做 紀錄一下這格的最好情形就會過了
推 hrs113355:對喔...  我當初讓他回頭了  難怪停不下來  囧"
→ LoganChien:參考程式碼我先拿下來，因為 Bob 說要讓部分同學補考，
→ LoganChien:所以我就先拿掉了。
※ 編輯: LoganChien      來自: 140.112.241.166      (11/11 20:02)