搜索题库

转载：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