首页 > 代码库 > 搜索题推荐
搜索题推荐
（转自网络博客）：
POJ
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*，双向广搜
poj1184聪明的打字员
如果觉得自己BFS的题做得差不多了,可以做一下这道题.作了这道题开始对BFS刮目相看了~花了整整一晚上写代码,改代码~
POJ 1069 -The Bermuda Triangle(难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1069
题意：用给定三角型填充六边形
解法：此题的思想上精华在于坐标化
ps:传说中比较bt，确实比较bt，主要很容易写错，我ac了，但程序没完全对....
POJ 1077 - Eight(中等，此题不做人生不完整)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1077
题意：八数码问题，超经典题
解法：广搜，A*，双向广搜
相关：http://hi.baidu.com/zfy0701/blog/item/7fcaba2c3d5425e98a1399cf.html
(百度之星的版本，强烈推荐)：http://acm.hnu.cn:8080/online/?action=problem&type=show&id=10466&courseid=0
POJ 1084 - Square Destroyer(中等，经典题)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1084
题意：把每个正方型看做集合中的元素，每个木棒看做是一个子集，求最小的子集覆盖
解法：dfs，A*，广搜肯定爆空间
POJ 1167 - The Buses(好难啊)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1167
题意：这道题综合了很多经典的深搜技巧，狂顶
解法：dfs
POJ 1190 - 生日蛋糕(基础，好题)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1190
题意：略
解法：dfs，题偏简单，但做出来还是有些感觉的
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 1376 - Robot(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1376
题意：略
解法：bfs，A*....
POJ 1475 - Pushing Boxes(中等，很推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1475
题意：推箱子游戏
解法：双重bfs(对箱子bfs 时
对人bfs)，A*
POJ 1945 - Power Hungry Cows(??)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1945
题意：略
解法：在一份解题报告中被列为难题，不过好好像写了个很简单很暴力的bfs就过了...速度还是有些慢，暂时想不到好的启发函数
POJ 2044 - Weather Forecast(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2044
题意：略
解法：广搜，dp，深搜
相关：http://hi.baidu.com/zfy0701/blog/item/d7b6490f847948e8ab6457c6.html
POJ 2286 - The Rotation Game(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2286
题意：略
解法：IDA*（迭代加深+上下界强剪
相关：http://hi.baidu.com/zfy0701/blog/item/ce0f802261bfbba14723e871.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 2426 Remainder(较难，=)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2426
题意：略，主要是数论部分比较容易让人抓狂
解法：bfs
相关：http://hi.baidu.com/zfy0701/blog/item/7fcaba2c3d5425e98a1399cf.html
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 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 2908 - Quantum(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2908
题意：其实就是找单源最短路径
解法：优先队列广搜(即dijkstra)，建议用位运算优化
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 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 3460 - Booksort(较难，很推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3460
题意：略
解法：IDA*，A*，DFS*
相关：http://hi.baidu.com/zfy0701/blog/item/5c5a404b0f73ecf582025ce4.html
POJ 3523 - The Morning after Halloween(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3523
题意：把所有机器人移到各自的位置，不能相撞或重合
解法：我的状态设计太暴力了：以所有机器人位置表示状态。然后用A*过，排倒数第几，郁闷。谁知道好的状态设计方法告诉我^_^
POJ 3633 - Copying DNA(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3633
题意：一个填充字符串的搜索题
解法：各种搜法皆宜
相关：算法的实现较挑战，我是参考了
http://www.wiskey86.cn/wordpress/?p=54
才搞定的
POJ 3635 full tank?(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3635
题意：最短路变形
解法：广搜
相关：http://hi.baidu.com/hnu_reason/blog/item/086e3dccfc8cb21600e9286b.html
HDU
1241 Oil Deposits (dfs的连通块个数)
1016 Prime Ring Problem(基础)
1584 蜘蛛牌(简单dfs,简单的剪枝,还有人用DP做(???))
1426 Sudoku Killer(练习递归的好题目 or Dancing links(???))
2510 符号三角形(打表题,写写打表程序还是不错的)
2553 N皇后问题(在n较小时,是经典的练习递归枚举的题目,n较大时状压(???))
3350 #define is unsafe (练习递归的好题目)(用结构体做返回值同时返回多个参数)
2821 Pusher( 看上去有点吓人,实际是简单题,搜就好了 )
2782 The Worm Turns(实际是简单题，搜就好了)
2616 Kill the monster(bfs+位运算 或 dfs 或 STL枚举全排列,总之，就是暴力……)
3500 Fling(实际是简单题,搜就好了)
2514 Another Eight Puzzle
1547 Bubble Shooter(思路是搜两次，dfs或bfs)
1175 连连看(dfs 或 bfs)
1728 逃离迷宫(和连连看一样)
剪枝：
典型题目：
1010 Tempter of the Bone(标准迷宫dfs，学习剪枝的开始)
学习了： 极限情况下的剪枝
奇偶性剪枝
(从(a,b)走到(c,d) 若a+b 与 c+d 奇偶性相同，需要走偶数步;否则走奇数步)
1455 Sticks(剪枝的好题目，黑书例题，坑了我好久的说)
学习了： 排序后解答树同层避免重复搜索
调整法(全集不行与子集肯定不行)
想法：每根小棍子都要被配对，当前情况下第一根无法配对，直接return
避免重复的题目还有：
1258 Sum It Up
2610 Sequence one( 让我认识了 stable_sort() )
2611 Sequence two( 在”2610 Sequence one”的基础上稍加修改即可)
Bfs:
一些简单题目:
1180 诡异的楼梯 (bfs可以加自己)
2102 A计划
1240 Asteroids! (单纯的三维bfs )
1253 胜利大逃亡 (单纯的三维bfs,加个剪枝: a+b+c-3>limit快了一倍)
1548 A strange lift
2717 Catch That Cow
1372 Knight Moves(或【双广】也可以)
1312 Red and Black
2612 Find a way
2531 Catch him
1252 Hike on a Graph
找状态hash判重很重要
帮助我理解“状态”的题目:
1732 Push Box(8维数组hash状态)
1429 胜利大逃亡(续)
理解：
一开始不知道怎么搜
和队友探讨，让我认识到 宽搜是很盲目，很随意的事情
搜就好了，碰到目标节点再说
“状态”练习题目：
1254 推箱子 ( bfs套bfs，走过的点还可以再走 )
1495 非常可乐(白书的例题—“倒水问题”)
2364 Escape
2579 Dating with girls(2)
1104 Remainder(自己在做的过程中逐渐找到了”状态”,和数论沾点边)
在bfs中经常碰到这样一类问题，加入节点的顺序与队列中节点的单调性不一致，这个时候用到优先队列来代替普通队列。我自己是用一个delay(延迟标记)，让这类节点先只向自己拓展，之后再向其他节点拓展。
“延迟”相关题目:
1240 Rescue (可以加自己,延迟入门)
4198 Quick out of the Harbour
1206 Ignatius and the Princess I(性价比高的宽搜题目)
2416 Treasure of theChimpIsland
2653 Waiting ten thousand years for Love
( 从这里引入了Dijkstra 最短路算法？？？？？？？ )
还有就是【双向广搜】
碰到了几道可以用双广解决的题目，用普通bfs也可以:
1401 Solitaire (【双广】，用普通bfs也能过)(好题)
1195 Open the Lock(普通bfs，状态，或【双广】)
一个问题：
判重用数组有时是严重浪费的，状态并没有那么多，但为了能完全表示，浪费了很多空间，甚至开不下数组，这个时候用hash技术……(还不太会%>_<%)
Dfs&Bfs:
1044 Collect More Jewels(好题)
这个题目提供了一种思路：
bfs预处理构造隐式图，然后dfs枚举所有情况求出最优解
1072 Nightmare(和上题同样的思路)
1983 Kaitou Kid - The Phantom Thief (2) (好题)(dfs枚举可能情况，然后bfs判定是否可行)
搜索题推荐