搜索练习题集

 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）

    

 

（2011/8/21）

ZOJ 2477 Magic Cube

三阶魔方旋转，因为最多5层，IDA*，因为每个面中间的位置是不变的构造h()为 (MAX(每个面周围的八个字符与中间字符不同的个数)+2)/3，然后暴搜就行了，话说转换数组确实好用，代码量少了几倍，0ms榜首

　　

（2011/8/25）

HDU 2953 Rubiks Cube

题解这里

  

HDU 3121 FreeOpen

题解这里

  

（2011/9/8）

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

小丽姐的题，状态表示和转移超级恶心，因为在一半的时候会有一个球和一个洞没掉，要用另外的标记表示，代码写的很烂很烂

 

  

  

（2012/7）

　　

UVa 12402 Parallel Missions

题解这里

 

CodeForces 83C Track

题解这里

http://www.cnblogs.com/ambition/archive/2011/07/25/search_plus.html

 

   

HDU3663 搜索，DLX
http://blog.csdn.net/yihuikang/article/details/8092172
HDU4778 搜索，alpha-beta
http://blog.csdn.net/waitfor_/article/details/14107121
HDU1813 搜索，IDA*
http://www.cnblogs.com/ambition/archive/2011/07/25/search_plus.html
HDU3900 搜索，状压BFS
http://www.cnblogs.com/ambition/archive/2011/07/25/search_plus.html
HDU1401 搜素，双广
http://www.cnblogs.com/ambition/archive/2011/07/25/search_plus.html

高级搜索题集  点击打开链接

Dancing Links题集 点击打开链接

极大极小过程题集  点击打开链接

POJ 1190 – 生日蛋糕(基础，好题)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1190
题意：略
解法：dfs，题偏简单，但做出来还是有些感觉的
POJ 1376 – Robot(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1376
题意：略
解法：bfs，A*….
POJ 2688 – Cleaning Robot(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2688
题意：bfs后转换为tsp问题
解法：bfs+dp，bfs+dfs
相关：http://hi.baidu.com/zfy0701/blog/item/ceb06f261749a6128a82a1b2.html
POJ 3322 – Bloxorz I(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3322
题意：略，这个游戏本身很好玩http://jandan.net/2008/01/24/bloxorz.html
解法：广搜，双向广搜
相关：http://hi.baidu.com/zfy0701/blog/item/d7b6490f847948e8ab6457c6.html
POJ 2308 – Dearboy’s Puzzle(中等，但做的人少?)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2308
题意：判断连连看是否有解
解法：DFS + BFS
相关：http://hi.baidu.com/zfy0701/blog/item/c62f41af65aa1fca7cd92afc.html
POJ 1324 – Holedox Moving(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1324
题意：略
解法：A*，dfs + 上界剪枝，广搜
相关：http://hi.baidu.com/zfy0701/blog/item/7fcaba2c3d5425e98a1399cf.html
http://hi.baidu.com/zfy0701/blog/item/a3c44ecc049b1c1501e92806.html
POJ 1084 – Square Destroyer(中等，经典题)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1084
题意：把每个正方型看做集合中的元素，每个木棒看做是一个子集，求最小的子集覆盖
解法：dfs，A*，广搜肯定爆空间
POJ 2449 Remmarguts’ Date(中等，强烈推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2449
题意：经典问题：K短路
解法：dijkstra+A*，方法很多
相关：http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144
POJ 2044 – Weather Forecast(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2044
题意：略
解法：广搜，dp，深搜
相关：http://hi.baidu.com/zfy0701/blog/item/d7b6490f847948e8ab6457c6.html
POJ 3635 full tank?(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3635
题意：最短路变形
解法：广搜
相关：http://hi.baidu.com/hnu_reason/blog/item/086e3dccfc8cb21600e9286b.html
POJ 3074 – Sudoku(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3074
题意：数独游戏，数据比2676强很多，但比3076弱
解法：用dfs回溯基本可过，不过每次应选择可能填的数字最少的格子搜
更快的方法是先转换成exact cover问题，然后用经典dancing links解决，
dancing links原始论文：http://lanl.arxiv.org/PS_cache/cs/pdf/0011/0011047v1.pdf
翻译：http://sqybi.com/works/dlxcn/
POJ 1475 – Pushing Boxes(中等，很推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1475
题意：推箱子游戏
解法：双重bfs(对箱子bfs 时 对人bfs)，A*
POJ 1077 – Eight(中等，此题不做人生不完整)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1077
题意：八数码问题，超经典题
解法：广搜，A*，双向广搜