首页 > 代码库 > 50道hdu基础搜索总结(转)

50道hdu基础搜索总结(转)

Dfs:

大部分是直接递归枚举,即求满足约束条件下的解,虽不用剪枝,但也需要代码能力。

练习递归枚举的题目:

1241       Oil Deposits (dfs的连通块个数)

1016       Prime Ring Problem

1584       蜘蛛牌(简单dfs,简单的剪枝,还有人用DP做(???))

1426       Sudoku Killer(练习递归的好题目 or Dancing links(???))

2510       符号三角形(打表题,写写打表程序还是不错的)

2553       N皇后问题(在n较小时,是经典的练习递归枚举的题目,n较大时状压(???))

2677       Dota all stars( 单纯练习递归的题目+串的处理 )

3350       #define is unsafe (练习递归的好题目)(用结构体做返回值同时返回多个参数)

3290       The magic apple tree(练习递归的题目,但有些坑)

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判定是否可行)