PTT數位生活區 / C_and_CPP (C/C++)

Re: [問題] ACM 704有什麼加速的辦法?

看板C_and_CPP (C/C++)作者 (伽藍之黑)時間15年前 (2011/06/04 19:34), 編輯推噓2(2推 0噓 9→)
留言11則, 3人參與, 最新討論串3/4 (看更多)
※ 引述《tkcn (小安)》之銘言： : ※ 引述《iamnotgm (伽藍之黑)》之銘言： : : 這題我試著用2-way BFS從input的state和finish的state展開 : : 只要兩個BFS中有相同的state就能知道走法 : : 可是光是一個state往下走8步能展開的state就有87381個 : 每一步都只有四種可能走法， : 走 8 步可能的 state 應該只有 4^8 = 65536， 那是最後一層的state數 在那之前的走7步,走6步...等等的state也要記下來吧 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.133.69.80
推
06/04 20:02, , 1F
說的沒錯，我現在知道你的 87381 從哪來的了
06/04 20:02, 1F
→
06/04 20:02, , 2F
不過扣掉重複的，實際數量會少非常多
06/04 20:02, 2F
→
06/04 20:03, , 3F
你現在最需要加速的應該就是檢查重複的部份了
06/04 20:03, 3F
→
06/04 21:37, , 4F
就算把檢查重複做到最快依然有將近1萬個不重複的state
06/04 21:37, 4F
→
06/04 21:38, , 5F
兩個BFS都有1萬個state全部檢查還是10^8
06/04 21:38, 5F
→
06/04 21:39, , 6F
10000 個其實挺少的不是嗎?
06/04 21:39, 6F
→
06/04 21:39, , 7F
呃，2-way BFS 不會把兩個複雜度相乘吧
06/04 21:39, 7F
→
06/04 21:41, , 8F
不然應該怎麼作?剛剛用hash寫倒是真的變快很多
06/04 21:41, 8F
推
06/05 12:12, , 9F
固定的那頭BFS結果做個排序，就可以二分搜尋。
06/05 12:12, 9F
→
06/05 12:15, , 10F
用hashing也可以，意思差不多。
06/05 12:15, 10F
→
06/05 12:16, , 11F
就算兩個for loop暴力比對還是可以通過 我跑2.5s
06/05 12:16, 11F
‣ 更多 iamnotgm 的文章
文章代碼(AID): #1DwXXZ3B (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 iamnotgm 的文章
文章代碼(AID): #1DwXXZ3B (C_and_CPP)