看板 [ Prob_Solve ]
討論串[問題] UVa 1505 - Flood-it! (BFS)
共 2 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] UVa 1505 - Flood-it! (BFS)
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者tobygameac (toby)時間12年前 (2013/01/11 21:39), 編輯資訊
1
0
3
內容預覽:
這是題目網址 : http://ppt.cc/kbk1. 遊戲網址 : http://floodit.appspot.com/. 找了一下資料，大部分好像是說要用A*之類的，. 還有一派是greedy，但greedy似乎沒辦法求optimal，. 不過這題的情況只有到 8*8 而且測資最多20組，.
(還有234個字)
#2
Re: [問題] UVa 1505 - Flood-it! (BFS)
推噓2(2推 0噓 3→)留言5則，0人參與, 最新作者seanwu (sean)時間12年前 (2013/01/13 19:00), 編輯資訊
0
0
3
內容預覽:
我用純BFS壓線過了(2.008s)，大致上有幾個重點. 1. 每次flood-fill太慢了，把每個區塊壓成一個點，相連的邊建好，在這個graph上做BFS. state是 S =「與原點連通的點集合」. 2. 維護好與S相鄰點的聯集 Xi(每種顏色分開)，這樣轉移state的速度比較快. 塗色i
(還有203個字)
首頁
上一頁
1
下一頁
尾頁