推 LPH66:四種而已嗎? 我怎麼感覺有十種? 06/04 17:04
→ LPH66:啊我搞錯了 @@" 06/04 17:05
※ 引述《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