http://acm.hdu.edu.cn/showproblem.php?pid=1813第一道是迷宮搜索
叫你找出一個序列能讓所有的點都按這個序列走出迷宮。。。
以前做的時候題意理解錯誤
昨天想了一下，這題的主要思想就是DFS出序列，讓所有的點都走出去
以題目的數據規模最差的情況要最深25層
所以剪枝是關鍵
我的剪枝方法是讓所有的出口入隊。。。
BFS預處理出每一個點到出口的最小距離
然后開始DFS序列。每走一步判斷所有的點在剩下的時間(即迭代加深的層數)內還能不能走出去
不行的話就回溯
直到找到答案。。
http://acm.hdu.edu.cn/showproblem.php?pid=1664第二道就不是很直白的搜索了。
TTBJ大大介紹我做的
一看很像之前做的一道
http://acm.hdu.edu.cn/showproblem.php?pid=1226超級密碼
感覺差不多
限制就是要最少的數字，個數相同的話要最小。
首先根據容斥原理知道個數最多為2(我也不知道，猜兩個數組可以全部表示，后來TTBJ和我說這是容斥原理)
所以用一個小小的迭代加深枚舉出兩組數列
1 2 3 4 5 6 7 8 9
和01 02 03 04 。。。。78 79 89
然后第一組(全部)進行BFS，可能會有很多個，比較得出最小的
第一組沒找到的話進行第二組的BFS。。。。
(這個BFS是按照余數來hash的)
然后就得出答案了。。。
http://acm.hdu.edu.cn/showproblem.php?pid=1067這道就是普通的BFS+字符hash
應為要保存全圖，所以比較難處理。。。
就用了字符hash。。
做的時候我掉進陷阱里導致MTL,TLE了N次。。。。郁悶
posted on 2009-03-12 17:07
shǎ崽 閱讀(571)
評論(0) 編輯 收藏 引用