※ 引述《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

感謝大大， 馬上來研究一下!level差太多， 完全沒想過這樣的bitwise等期末考完再來研究， 感謝大大XD

someone shows it's NP-hard, but I don't review that paperhttp://arxiv.org/pdf/1001.4420v3.pdf