作者seanwu (sean)
看板Prob_Solve
标题Re: [问题] UVa 1505 - Flood-it! (BFS)
时间Sun Jan 13 19:00:25 2013
※ 引述《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)
1F：推 tobygameac:感谢大大， 马上来研究一下! 01/13 19:08
2F：推 tobygameac:level差太多， 完全没想过这样的bitwise 01/13 19:36
3F：→ tobygameac:等期末考完再来研究， 感谢大大XD 01/13 19:36
4F：→ Leon:someone shows it's NP-hard, but I don't review that paper 01/14 15:24