看板 [ C_and_CPP ]
討論串[問題] ACM 704有什麼加速的辦法?
共 4 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#4
Re: [問題] ACM 704有什麼加速的辦法?
推噓0(0推 0噓 2→)留言2則，0人參與, 最新作者tkcn (小安)時間15年前 (2011/06/04 21:46), 編輯資訊
0
0
0
內容預覽:
GCJ 快開始了，簡短講一下 (逃). 先從一端 BFS 八層，產生那將近一萬個 state，加入 hash table，. 再從另一端 BFS，每到一個新 state 都檢查是否存在 hash table 中。. 很顯然複雜度只是兩次 BFS，並沒有相乘 (前題是利用 hash table 檢查為
(還有204個字)
#3
Re: [問題] ACM 704有什麼加速的辦法?
推噓2(2推 0噓 9→)留言11則，0人參與, 最新作者iamnotgm (伽藍之黑)時間15年前 (2011/06/04 19:34), 編輯資訊
0
0
0
內容預覽:
那是最後一層的state數. 在那之前的走7步,走6步...等等的state也要記下來吧. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 220.133.69.80.
#2
Re: [問題] ACM 704有什麼加速的辦法?
推噓1(1推 0噓 1→)留言2則，0人參與, 最新作者tkcn (小安)時間15年前 (2011/06/04 13:58), 編輯資訊
0
0
0
內容預覽:
每一步都只有四種可能走法，. 走 8 步可能的 state 應該只有 4^8 = 65536，. 實際上因為其中一種走法都是回到上一步，. 再扣掉同一種走法連續六次形成的重複，. state 應該不超過 3^8 = 6561。. 這裡如果用 hash table，檢查就是 O(1) 了. --. ※
#1
[問題] ACM 704有什麼加速的辦法?
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者iamnotgm (伽藍之黑)時間15年前 (2011/06/04 13:51), 編輯資訊
0
0
0
內容預覽:
這題我試著用2-way BFS從input的state和finish的state展開. 只要兩個BFS中有相同的state就能知道走法. 可是光是一個state往下走8步能展開的state就有87381個. 試著在每作到一個state時檢查所有走過的state看這個state是否走過. 結果是948
首頁
上一頁
1
下一頁
尾頁