POJ搜索题目列表

• 这不是我原创的，是从网上找到的，跟大家分享一下。
• 后边标的难度是对于小菜而言的，像例如说applepi(杜神牛)这样的神牛除外。
• 放到这里还有一个原因是为了自己看着方便，因为我搜索较弱，要多加练习。
• 红的是我已经做过并AC的题，蓝的是我做过但还没AC，或正在做的题。

POJ 1069 -The Bermuda Triangle(难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1069
题意：用给定三角型填充六边形
解法：此题的思想上精华在于坐标化

POJ 1077 – Eight(中等，此题不做人生不完整)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1077
题意：八数码问题，超经典题
解法：广搜，A*，双向广搜 
本博客题解：http://www.lydshy.com/wordpress/123

POJ 1084 – Square Destroyer(中等，经典题)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1084
题意：把每个正方型看做集合中的元素，每个木棒看做是一个子集，求最小的子集覆盖
解法：dfs，A*，广搜肯定爆空间
本博客题解：http://www.lydshy.com/wordpress/125

POJ 1167 – The Buses(难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1167
题意：这道题综合了很多经典的深搜技巧，狂顶
解法：dfs
本博客题解：http://www.lydshy.com/wordpress/63

POJ 1190 – 生日蛋糕(基础，好题)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1190
题意：略
解法：dfs，题偏简单，但做出来还是有些感觉的
本博客题解：http://www.lydshy.com/wordpress/32

POJ 1324 – Holedox Moving(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1324
题意：略
解法：A*，dfs + 上界剪枝，广搜

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*
本博客题解：http://www.lydshy.com/wordpress/61

POJ 1945 – Power Hungry Cows(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1945
题意：略
解法：略

POJ 2044 – Weather Forecast(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2044
题意：略
解法：广搜，dp，深搜
本博客题解：http://www.lydshy.com/wordpress/55

POJ 2286 – The Rotation Game(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2286
题意：略
解法：IDA*（迭代加深+上下界剪枝）
本博客题解：http://www.lydshy.com/wordpress/127

POJ 2308 – Dearboy’s Puzzle(中等，但做的人少?)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2308
题意：判断连连看是否有解
解法：DFS + BFS

POJ 2426 Remainder(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2426
题意：略，主要是数论部分比较容易让人抓狂
解法：bfs

POJ 2449 Remmarguts’ Date(中等，强烈推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2449
题意：经典问题：K短路
解法：dijkstra+A*，方法很多
本博客题解：http://www.lydshy.com/wordpress/118

POJ1072 PuzzleOut（较难，强烈推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1072
题意：有关解密的
解法：Trie+DFS+剪枝
本博客题解：http://www.lydshy.com/wordpress/58

POJ2222 DeeperBlue（中等）
题意：一个国际象棋盘上放着几个子，问最少去掉几个可以不互相攻击。主要考察细心，题目跟题号的性质相符（比较2）
解法：dfs、暴力枚举
本博客题解：http://www.lydshy.com/wordpress/53

POJ 2688 – Cleaning Robot(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2688
题意：bfs后转换为tsp问题
解法：状态压缩BFS。转化为TSP的话极易超时。
 本博客题解：http://www.lydshy.com/wordpress/120

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解决。

POJ 3322 – Bloxorz I(基础)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3322
题意：略，这个游戏本身很好玩（http://jandan.net/2008/01/24/bloxorz.html）
解法：广搜，双向广搜。

POJ 3460 – Booksort(较难，很推荐)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3460
题意：略
解法：IDA*，A*，双向BFS
本博客题解：http://www.lydshy.com/wordpress/129

POJ 3523 – The Morning after Halloween(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3523
题意：把所有机器人移到各自的位置，不能相撞或重合

POJ 3633 – Copying DNA(较难)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3633
题意：一个填充字符串的搜索题
解法：各种搜法皆宜

POJ 3635 full tank?(中等)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3635
题意：最短路变形
解法：广搜
本博客题解：http://www.lydshy.com/wordpress/36