作者LoganChien (簡子翔)
看板b97902HW
標題[計程] 單班期中考的第二題的參考程式碼
時間Fri Nov 7 02:15:06 2008
這二個晚上被計程期中考的第二題搞的心神不定，因為我覺得第二
題我應該有能力寫出來，可是沒有寫出來。所以今晚我花了一些時
間寫第二題。我用了三種方法來寫︰
(按 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
1F：推 dennis2030:專業文! 不過可以請問BFS跟DFS是什麼嗎? 看不懂Q口Q 11/07 02:17
2F：→ dennis2030:是某種演算法嗎? 11/07 02:17
3F：推 averangeall:如果有修離散的人 就會知道XDDD 11/07 02:21
4F：→ LoganChien:DFS 就是每到某一格，我們會先試四周的某一格，再看剛 11/07 02:22
5F：→ LoganChien:再看剛才選的那一格的四周。直到走投無路才會回頭試下 11/07 02:23
6F：→ LoganChien:一個方向的格子。 11/07 02:23
7F：→ LoganChien:BFS 就是把第一格四周的格子列入清單，然後從清單最上 11/07 02:25
8F：→ LoganChien:面的找下一個，下一個四周又會被加到清單底端。 11/07 02:26
9F：推 sa072686:提BFS+Priority Queue太艱深了吧… 11/07 03:09
※ 編輯: LoganChien 來自: 140.112.241.166 (11/07 03:43)
10F：→ anfranion:DFS = Depth First Search 深度優先搜尋 11/07 05:42
11F：→ anfranion:BFS = Breadth First Search 廣度優先搜尋 11/07 05:43
12F：→ anfranion:不過這...好像不適合這麼早就提這些吼囧a 11/07 05:44
13F：→ anfranion:這是兩種演算法沒錯～離散只是有提到而已 11/07 05:44
14F：推 iForests:其實只是求 (1,1) 到某一格 f 的最短路徑 11/07 10:12
15F：推 iForests:並沒有你說的那麼難。 11/07 10:16
16F：→ chenaren:超難 >.< 11/07 11:37
17F：推 godgunman:有個關鍵是, 一個點的分支很小, 頂多三方向 (不會回頭) 11/07 12:36
18F：→ godgunman:所以直接做 紀錄一下這格的最好情形就會過了 11/07 12:37
19F：推 hrs113355:對喔... 我當初讓他回頭了 難怪停不下來 囧" 11/07 13:57
20F：→ LoganChien:參考程式碼我先拿下來，因為 Bob 說要讓部分同學補考， 11/11 20:01
21F：→ LoganChien:所以我就先拿掉了。 11/11 20:02
※ 編輯: LoganChien 來自: 140.112.241.166 (11/11 20:02)