作者bc5678 ( )
看板C_and_CPP
標題[ACM ][TLE] 838 Worm World
時間Sat Sep 19 22:14:19 2009
UVa 838 Worm World
原文題目網址
http://online-judge.uva.es/p/v8/838.html
中文題目網址, 看圖就能很明白知道題目在問什麼了
http://www.tcgs.tc.edu.tw/~sagit/luckycat/q838.htm
題目大意:
給定 N*N 方陣 (0 < N <= 12), 方陣裡面的數字介於0~1000,
在路徑只能左右移動或上下移動的條件下, 找出擁有不重複數字的最長路徑之長度
/***** Sample Input *****/
2
3
1 2 1
2 3 4
3 2 1
8
6 8 18 15 24 20 2 20
6 2 15 2 17 15 3 7
0 11 18 16 20 15 1 11
6 2 6 13 4 17 20 16
5 12 7 2 3 5 18 23
7 13 3 2 2 11 4 23
16 23 10 2 4 12 5 20
17 12 10 1 13 12 6 20
/***** Sample Output *****/
4
20
==========
我自己的方法是針對每一位置N(x, y)做brute forth搜尋
搜尋的深度不會超過M (M = min(數字種類, 方陣大小) )
找到之後就將此路徑記下, 以後有其他位置起始的路徑要通過時就拿來reuse
如果找到的路徑長度已經等於M, 那自然就是直接回傳答案
對於上面兩個測資是沒問題, 但是跑自己做的一個測資時就變得極慢
1
12
0 1 2 3 4 5 6 7 8 9 10 11
12 13 14 15 16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31 32 33 34 35
36 37 38 39 40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69 70 71
72 73 74 75 76 77 78 79 80 81 82 83
84 85 86 87 88 89 90 91 92 93 94 95
96 97 98 99 100 101 102 103 104 105 106 107
108 109 110 111 112 113 114 115 116 117 118 119
120 121 122 123 124 125 126 127 128 129 129 129
132 133 134 135 136 137 138 139 140 129 142 143
因為光是從N(0, 0)出發時brute forth所產生的路徑就太多了
不知是否有人有想出更好的方法或是更好的終止條件?
補上TLE的code :
http://codepad.org/KOyonZNk
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 112.104.27.222
1F：推 goliathplus:用 DP 解 09/19 22:33
2F：→ bc5678:應該沒辦法單純地切sub problem吧, 願聞其詳? 09/19 22:38
3F：→ takingblue:backtracking 09/19 23:52
Lucky貓的提示也是這個, 不過不知詳細怎麼做呢?
http://203.64.52.212/~ACM/
※ 編輯: bc5678 來自: 123.204.164.164 (09/21 00:55)
4F：推 cutecpu:65 ~ 72 行 的 reuse 拿掉，直接跑 74 ~ 77 行的遞迴 09/21 17:03
5F：→ cutecpu:127 行 改成 if(n) printf("\n"); 09/21 17:03
6F：→ bc5678:問題已解決, 感謝熱心的CPU 09/21 19:18
7F：推 DJWS:想請教一樓所說的DP解的詳細內容，謝謝。 :) 09/22 09:22