推 tobygameac:感謝大大， 馬上來研究一下! 01/13 19:08
推 tobygameac:level差太多， 完全沒想過這樣的bitwise 01/13 19:36
→ tobygameac:等期末考完再來研究， 感謝大大XD 01/13 19:36
→ Leon:someone shows it's NP-hard, but I don't review that paper 01/14 15:24
※ 引述《tobygameac (toby)》之銘言：
: 這是題目網址 : http://ppt.cc/kbk1
: 遊戲網址 : http://floodit.appspot.com/
: 找了一下資料，大部分好像是說要用A*之類的，
: 還有一派是greedy，但greedy似乎沒辦法求optimal，
: 不過這題的情況只有到 8*8 而且測資最多20組，
: 跟那些文章追求的可能不大一樣，
: 想請問一下單純的BFS有沒有可能不超時?
我用純BFS壓線過了(2.008s)，大致上有幾個重點
1. 每次flood-fill太慢了，把每個區塊壓成一個點，相連的邊建好，在這個graph上做BFS
state是 S =「與原點連通的點集合」
2. 維護好與S相鄰點的聯集 Xi(每種顏色分開)，這樣轉移state的速度比較快
塗色i時，S'=S∪Xi，for each j Xj'=Xj∪Yj (Yj是與S'\S相鄰的色j點)
3. state可以壓成 64bit integer，這樣 union 可以 O(1) 做好
4. STL map有點慢，我用hash來檢查有沒有走過 (一開始用set<long long>會超時)
補一下code: http://ideone.com/0ziGa6
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.4.194
※ 編輯: seanwu 來自: 140.112.4.194 (01/13 19:01)
※ 編輯: seanwu 來自: 140.112.4.194 (01/13 19:02)