Re: [問題] UVa 1505 - Flood-it! (BFS)
看板Prob_Solve (計算數學 Problem Solving)作者seanwu (sean)時間12年前 (2013/01/13 19:00)推噓2(2推 0噓 3→)留言5則, 2人參與討論串2/2 (看更多)
※ 引述《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)
推
01/13 19:08, , 1F
01/13 19:08, 1F
推
01/13 19:36, , 2F
01/13 19:36, 2F
→
01/13 19:36, , 3F
01/13 19:36, 3F
→
01/14 15:24, , 4F
01/14 15:24, 4F
→
01/14 15:24, , 5F
01/14 15:24, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
