作者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)