Re: [問題] ACM 704有什麼加速的辦法?
※ 引述《iamnotgm (伽藍之黑)》之銘言：
: 這題我試著用2-way BFS從input的state和finish的state展開
: 只要兩個BFS中有相同的state就能知道走法
: 可是光是一個state往下走8步能展開的state就有87381個
每一步都只有四種可能走法，
走 8 步可能的 state 應該只有 4^8 = 65536，
實際上因為其中一種走法都是回到上一步，
再扣掉同一種走法連續六次形成的重複，
state 應該不超過 3^8 = 6561。
: 試著在每作到一個state時檢查所有走過的state看這個state是否走過
: 結果是9489個不重複的state
這裡如果用 hash table，檢查就是 O(1) 了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.78.231
推
06/04 17:04, , 1F
06/04 17:04, 1F
→
06/04 17:05, , 2F
06/04 17:05, 2F
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
