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

[iamnotgm (伽藍之黑)]

※ 引述《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
推 tkcn:說的沒錯，我現在知道你的 87381 從哪來的了
→ tkcn:不過扣掉重複的，實際數量會少非常多
→ tkcn:你現在最需要加速的應該就是檢查重複的部份了
→ iamnotgm:就算把檢查重複做到最快依然有將近1萬個不重複的state
→ iamnotgm:兩個BFS都有1萬個state全部檢查還是10^8
→ tkcn:10000 個其實挺少的不是嗎?
→ tkcn:呃，2-way BFS 不會把兩個複雜度相乘吧
→ iamnotgm:不然應該怎麼作?剛剛用hash寫倒是真的變快很多
推 DJWS:固定的那頭BFS結果做個排序，就可以二分搜尋。
→ DJWS:用hashing也可以，意思差不多。
→ DJWS:就算兩個for loop暴力比對還是可以通過  我跑2.5s