※ 引述《tobygameac (toby)》之铭言：
: 这是题目网址 :

: 游戏网址 : 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