搜尋題庫

轉載：http://blog.csdn.net/acm_cxlove/article/category/1161578

HDU 1813 Escape from Tetris IDA*搜尋

HDU 3459 Rubik 2×2×2 二階魔方還原(IDA*)

HDU 1401 Solitaire 雙向BFS

HDU 3567 Eight II 八數位（2）

ZOJ 2477 Magic Cube 三階魔方還原（IDA*）

HDU 4012 Paint on a Wall 搜尋

POJ 1085 Triangle War（博弈，極大極小搜尋+alpha_beta剪枝）

POJ 1568 Find the Winning Move(極小極大搜尋+alpha-beta剪枝)

POJ 3317 Stake Your Claim（極大極小搜尋+alpha-beta剪枝）

ZOJ 3617 Riding Alone for Thousands of Miles(貪心+線段樹)

ZOJ 3652 MAZE（BFS）

HDU 4127 Flood-it!(11年福州 IDA*搜尋)

HDU 4394 Digital Square （BFS）

HDU 4574 Bombs (枚舉+搜尋)

HDU 2234 無題I IDA*搜尋

HDU 2918 Tobo or not Tobo IDA*搜尋

HDU 1560 DNA sequence IDA*搜尋

HDU 1667 The Rotation Game IDA*搜尋

HDU 1043 八數位問題 A*搜尋

HDU 1254 推箱子（搜尋）

HDU 2128 Tempter of the Bone II(BFS)

HDU 搜尋進階專題

去年聽ReDow講A*,IDA*，當時小菜（現在也是），就沒把那些東西列在學習範圍内，前些天LCY讓我講搜尋進階，就做了幾題，分享下做題感受～～

HDU 1043 Eight

涉及到人生完不完整的一道題，有位大神總結出了八數位的8重境界，可見其經典程度無出其右～～

A*: 因為每次移動都會影響一個點的曼哈頓距離（不算x），構造h()為所有數字塊的曼哈頓距離和，用逆序數hash（算x），根據逆序數奇偶性（不算x）減掉無法到達的情況，A*跑了656ms，POJ 16ms，在構造優先隊列時當f相同時按照g值從大到小排序，這樣又是一個很給力的減枝，HDU 468ms，POJ 0ms 

單廣預處理: 從最終狀态向所有狀态搜尋，記錄前驅，然後直接輸出就好了，HDOJ 93ms POJ 313ms

IDA*: 和A*相同的h()函數，跑了1s+，POJ 63ms，500k的記憶體是其優勢

HDU 1667 The Rotation Game

IDA*的入門題目，狀态過多容易超記憶體，正好展現了IDA*的優勢，每次操作移動能使一個數字進入中間的八個位置，是以構造h()=8-max(1,2,3在中間8個位置的個數)，自己的寫的太挫了，跑了1s多，後來問ReDow大神要了代碼，171ms

HDU 2234 無題I

IDA*，開始寫挫了，加了A*還是逾時，又亂搞了好久才過，後來重寫了一遍，2s+；每次移動改變四個點的位置，即h()=(最少可能的橫向或縱向不在位置上的點的個數+3)/4 )；看到CY 1.3s 求代碼得知是普通的dfs，資料水了...

HDU 1560 DNA sequence

IDA*: 容易看出最少步數肯定是大于等于最大字元長度的，是以就構造 h() 為所有剩餘長度的最大值，2s

單廣: 去年寫了一個很挫很挫的單廣，在各種TLE，MLE，RE之後終于4984ms過掉了(限5s)，今年吓怕了不敢寫，後來向hh要了他的125ms的代碼，單廣，就模仿hh的代碼，很裝逼的用8進制壓縮，結果狀态由300w驟升至1500w，還要用bitset來hash，跑400+ms，就不拿出來丢人了；hh的代碼直接開int進行hash，每組cas的hash值不同，這樣就省去了每次初始化的消耗，hh的代碼～

HDU 1813  Escape from Tetris

IDA*的好題目，開始時沒想到A*方法，就直接暴力的送出了一次，如願逾時，随便YY了一組case就跑不出結果，然後想到可以求出某個位置逃出的最少步數，然後在構造 h() 為所有點逃離迷宮的最少步數的最大值，然後很容易就能A掉了

HDU 2918 Tobo or not Tobo

這題步數最多隻有9步，果斷IDA*，因為每步會改變四個數字的曼哈頓距離，是以h()構造為 (曼哈頓距離和+3)/4，送出竟然居首了

這題也可以用廣搜預處理來寫，廣搜九層，然後詢問時直接輸出就好了，也可以0ms，但記憶體肯定要比IDA*大

HDU 3459 Rubik 2×2×2

這題是ReDow推薦的一道好玩的題目(ReDow大神無壓力的占據着第一的位置)，用IDA*寫，很容易想到一個很不給力的A*剪枝：因為有一塊始終不會改變，可以确定3個面的顔色，根據這3個面的顔色又可以确定另外3個面的顔色，也就是說最終狀态是确定的，這樣可以在遞歸到最後3層時稍微起到點作用。跑sample都很吃力（這題都不要求是最優解，sample 20+步，而最優的16層就出結果了，還以為寫錯了，查代碼查了半天- -），無意中送出了一下，sample都要卡一下下的代碼竟然過了，200+ms。然後測了下不加A*的代碼，跑了2s，看來這個A*還是很給力的

A*、IDA*的也就這些了，别的一些搜尋題目～

HDU 1401 Solitaire

一道經典的雙廣題目，去年暑假廢了好大功夫寫了一個很挫的200+ms的代碼，今年再寫就得心應手許多：

記錄排序後的四個點的坐标作為目前狀态，即8個小于8的數，用二進制(或者說是八進制)進行狀态壓縮，有近2kw種狀态，用bitset進行hash，15ms過掉

HDU 1430  魔闆

資料量很大的一道題，雙廣要跑2s+而且還要記錄路徑，代碼過煩了，參考hh部落格知道預處理的方法：

由于隻是8種顔色，是以标号就無所謂了，對起始狀态重新修改标号為 12345678(别的也行)，對目标狀态标号做相應的修改，先預處理出12345678到所有狀态的路徑，記錄所有狀态的pre值，直接輸出即可；其實以目标狀态為标準去修改起始狀态标号可以省去逆序輸出路徑的麻煩

HDU 3567 Eight II

Eight 的加強版

做過魔闆這題再做這題，腦子裡就隻有預處理的方法了，因為這題有一個特殊的點X，是以枚舉X的位置，打出9張前驅表，用魔闆題一樣的方法将兩個狀态的對應标号轉化，輸出就好了，800ms

HDU 2691 2-Dimensional Rubik's Cube

這題是3459的加強版，雙廣，狀态太多了，試了幾種字元串hash都有沖突，sample都出不來，隻好改用map，跑了3s+，後來問了hh，因為隻有六種顔色，可以将每種狀态轉換成一個long long型，6^24，可以用散清單hash，改成散清單之後瞬間快很多，600+ms

HDU 3278 Puzzle

在hh部落格看到的一個月賽題目，雖然做之前就知道IDA*過不了，但還是想敲一下，畢竟碼短、簡單，結果不料WA到死，一直找不到錯，隻好改方法；這題看起來跟1667題相似，但那題每次隻會産生8種狀态，這題有20種，普通的方法很難AC，G了一下原來可以預處理：假定W是最終在中間位置的顔色，那麼就把G和B當作同一種顔色，這樣就可以通過二進制壓縮把狀态用一個整形數字表示，預處理出所有狀态之後取三種顔色的最小值即可，2kw的數組開起來确實很吃力，使用char型終于水過了這題～～（後來看下背景，竟然有十萬組資料，搞毛啊，害我IDA*狂交還報WA T_T）

ZOJ 2477 Magic Cube

三階魔方旋轉，因為最多5層，IDA*，因為每個面中間的位置是不變的構造h()為 (MAX(每個面周圍的八個字元與中間字元不同的個數)+2)/3，然後暴搜就行了，話說轉換數組确實好用，代碼量少了幾倍，0ms榜首

HDU 2953 Rubiks Cube

HDU 3121 FreeOpen

HDU 4012 Paint on a Wall

另外補兩道以前做的幾道題的題解：

HDU 3900 Unblock me

比賽時候一直搞這題，最終導緻全隊悲劇 - -

開始時用IDA*去做，結果sample跑了十分鐘都沒出，題目中的條件好多沒用上，想不出方法來，後來看了題解，太佩服這題出題人了，狀态壓縮用到了極緻的神題

因為隻有1*2,1*3,2*1,3*1幾種塊，又有水準條隻能水準移豎直條隻能豎直移，那麼就可以看出每塊的位置隻有四五種情況，用八進制儲存每一塊的位置情況，根據靜态記錄的每一塊的行或列算出他的實際位置，然後就是各種二進制操作了

HDU 3085 Nightmare II

二日月教主的題，開始一看到800*800就開始腦殘了，去想IDA*，後來IDA*寫一半發現根本不用記錄狀态的 = =||，這題目就一個簡單的雙向廣搜，也有人用三廣去做，惡魔可以穿牆的，是以直接根據坐标計算就好了

HDU 3309 Roll The Cube

小麗姐的題，狀态表示和轉移超級惡心，因為在一半的時候會有一個球和一個洞沒掉，要用另外的标記表示，代碼寫的很爛很爛

UVa 12402 Parallel Missions

CodeForces 83C Track