第三章

# [返回目录](https://www.luogu.com.cn/training/441063) ## 3.1 BFS和DFS基础 ### 例3.1 [全球变暖](https://www.lanqiao.cn/problems/178/learning/) #### 课后习题: [力扣DFS题单](https://leetcode.cn/tag/depth-first-search/problemset/) [力扣BFS题单](https://leetcode.cn/tag/breadth-first-search/problemset/) [P1219 [USACO1.5] 八皇后 Checker Challenge](https://www.luogu.com.cn/problem/P1219) [P1019 [NOIP2000 提高组] 单词接龙](https://www.luogu.com.cn/problem/P1019) [P5194 [USACO05DEC] Scales S](https://www.luogu.com.cn/problem/P5194) [P5440 【XR-2】奇迹](https://www.luogu.com.cn/problem/P5440) [P1978 集合](https://www.luogu.com.cn/problem/P1978) [P1162 填涂颜色](https://www.luogu.com.cn/problem/P1162) [P1443 马的遍历](https://www.luogu.com.cn/problem/P1443) [P3956 [NOIP2017 普及组] 棋盘](https://www.luogu.com.cn/problem/P3956) [P1032 [NOIP2002 提高组] 字串变换](https://www.luogu.com.cn/problem/P1032) [P1126 机器人搬重物](https://www.luogu.com.cn/problem/P1126) [poj 2488 A Knight's Journey](http://poj.org/problem?id=2488) [poj 3083 Children of the Candy Corn](http://poj.org/problem?id=3083) [poj 3009 Curling 2.0](http://poj.org/problem?id=3009) [poj 1321 棋盘问题](http://poj.org/problem?id=1321) [poj 3278 Catch That Cow](http://poj.org/problem?id=3278) [poj 1426 Find The Multiple](http://poj.org/problem?id=1426) [poj 3126 Prime Path](http://poj.org/problem?id=3126) [poj 3414 Pots](http://poj.org/problem?id=3414) [poj 2251 Dungeon Master](http://poj.org/problem?id=2251) ## 3.2 剪枝 ### 例3.2 [跳蚱蜢](https://www.lanqiao.cn/problems/642/learning/) ### 例3.3 [Catch That Cow](http://poj.org/problem?id=3278) ### 例3.4 [[USACO06FEB] Backward Digit Sums G/S](https://www.luogu.com.cn/problem/P1118) ### 例3.5 [吃奶酪](https://www.luogu.com.cn/problem/P1433) ### 例3.6 [Tempter of the Bone](https://acm.hdu.edu.cn/showproblem.php?pid=1010) ### 例3.7 [小木棍](https://www.luogu.com.cn/problem/P1120) ### 例3.8 [Sequence one](https://acm.hdu.edu.cn/showproblem.php?pid=2610) ### 例3.9 [Sequence two](https://acm.hdu.edu.cn/showproblem.php?pid=2611) ### 例3.10 [Sudoku](http://poj.org/problem?id=2676) ### 例3.11 [[NOIP2009 提高组] 靶形数独](https://www.luogu.com.cn/problem/P1074) #### 课后习题: [P1120 小木棍](https://www.luogu.com.cn/problem/P1120) [P1312 [NOIP2011 提高组] Mayan 游戏](https://www.luogu.com.cn/problem/P1312) [P1074 [NOIP2009 提高组] 靶形数独](https://www.luogu.com.cn/problem/P1074) [poj 1010 STAMPS](http://poj.org/problem?id=1010) [poj 2362 Square](http://poj.org/problem?id=2362) [poj 1011 Sticks](http://poj.org/problem?id=1011) [poj 1416 Shredding Company](http://poj.org/problem?id=1416) [poj 2676 Sudoku](http://poj.org/problem?id=2676) [poj 1129 Channel Allocation](http://poj.org/problem?id=1129) [poj 1120 A New Growth Industry](http://poj.org/problem?id=1120) [poj 3411 Paid Roads](http://poj.org/problem?id=3411) [poj 1724 ROADS](http://poj.org/problem?id=1724) ## 3.3 洪水填充 ### 例3.12 [Red and Black](https://acm.hdu.edu.cn/showproblem.php?pid=1312) ### 例3.13 [The Wedding Juicer](http://poj.org/problem?id=2227) ### 例3.14 [[NOIP2010 提高组] 引水入城](https://www.luogu.com.cn/problem/P1514) #### 课后习题: [hdu 5319 Painter](https://acm.hdu.edu.cn/showproblem.php?pid=5319) [hdu 4574 Bombs](https://acm.hdu.edu.cn/showproblem.php?pid=4574) [hdu 1240 Asteroids!](https://acm.hdu.edu.cn/showproblem.php?pid=1240) [hdu 6113 度度熊的01世界](https://acm.hdu.edu.cn/showproblem.php?pid=6113) [P1506 拯救oibh总部](https://www.luogu.com.cn/problem/P1506) [P1162 填涂颜色](https://www.luogu.com.cn/problem/P1162) [P1649 [USACO07OCT] Obstacle Course S](https://www.luogu.com.cn/problem/P1649) [poj 1979 Red and Black](http://poj.org/problem?id=1979) [poj 3026 Borg Maze](http://poj.org/problem?id=3026) [poj 2157 Maze](http://poj.org/problem?id=2157) ## 3.4 BFS与最短路 ### 例3.15 [迷宫](https://www.lanqiao.cn/problems/602/learning/) ## 3.5 双向广搜 ### 例3.16 [Open the Lock](https://acm.hdu.edu.cn/showproblem.php?pid=1195) ### 例3.17 [Solitaire](https://acm.hdu.edu.cn/showproblem.php?pid=1401) ### 例3.18 [Eleven puzzle](https://acm.hdu.edu.cn/showproblem.php?pid=3095) ### 例3.19 [[NOIP2002 提高组] 字串变换](https://www.luogu.com.cn/problem/P1032) ### 难题:[poj 3131 Cubic Eight-Puzzle](http://poj.org/problem?id=3131) #### 课后习题: [P3067 [USACO12OPEN] Balanced Cow Subsets G](https://www.luogu.com.cn/problem/P3067) [P4799 [CEOI2015 Day2] 世界冰球锦标赛](https://www.luogu.com.cn/problem/P4799) [P5195 [USACO05DEC] Knights of Ni S](https://www.luogu.com.cn/problem/P5195) ## 3.6 BFS与优先队列 ### 例3.20 [最短路径](https://www.lanqiao.cn/problems/1122/learning/) ## 3.7 BFS与双端队列 ### 例3.21 [[BalticOI 2011 Day1] Switch the Lamp On](https://www.luogu.com.cn/problem/P4667) ## 3.8 (A*)算法 ### 例3.22 [Remmarguts' Date](http://poj.org/problem?id=2449) ### 例3.23 [Power Hungry Cows](http://poj.org/problem?id=1945) ## 3.9 IDDFS和(IDA*) ### 例3.24 [Power Calculus](http://poj.org/problem?id=3134) #### 课后习题: [hdu 1560 DNA sequence](https://acm.hdu.edu.cn/showproblem.php?pid=1560) [hdu 1667 The Rotation Game](https://acm.hdu.edu.cn/showproblem.php?pid=1667) [hdu 4127 Flood-it!](https://acm.hdu.edu.cn/showproblem.php?pid=4127) [P1032 [NOIP2002 提高组] 字串变换](https://www.luogu.com.cn/problem/P1032) [P2346 四子连棋](https://www.luogu.com.cn/problem/P2346) [P2324 [SCOI2005] 骑士精神](https://www.luogu.com.cn/problem/P2324) [P2534 [AHOI2012] 铁盘整理](https://www.luogu.com.cn/problem/P2534)