DFS递归实现 栈实现 编程技巧

DFS递归实现 栈实现 10网络李卿 DFS是神马东西 深度优先搜索算法 Depth First Search 是搜索算法的一种 是沿着树的深度遍历树的节点 尽可能深的搜索树的分支 当节点v的所有边都己被探寻过 搜索将回溯到发现节点v的那条边的起始节点 这一过程一直进行到已发现从源节点可达的所有节点为止 如果还存在未被发现的节点 则选择其中一个作为源节点并重复以上过程 整个进程反复进行直到所有节点都被访问为止 属于盲目搜索 因发明 深度优先搜索算法 霍普克洛夫特与陶尔扬共同获得计算机领域的最高奖 图灵奖 via 维基百科 先说点儿别的 穷举法 经典问题 百钱买百鸡 公鸡5元一只 母鸡3元一只 小鸡1元3只 现在有100元买百鸡 每种至少买一只 编程输出所有的可能性 穷举法 小鸡 母鸡 公鸡 穷举法 遍历出所有可能的情况 逐个判断哪些是符合问题所要求的条件 从而得出问题的解答 优点 结构简单 容易理解 便于用程序实现 缺点 是一种比较盲目的搜索方法 时间消耗大 递归与分治 递归 指在函数的定义中使用函数自身的方法 加终止条件 递归与分治 更经典的问题 求N的阶乘 递归与分治 分治法 将一个难以直接解决的大问题 分割成一些规模较小的相同问题 以便各个击破 分而治之 栈 后进先出 与递归关系亲密 STL中的栈 多维数组 一维数组 二维数组 三维数组 DFS DFS 能用来干什么 DFS 怎样利用DFS来走迷宫 走走看 起点 终点 用DFS怎么走 深搜深搜 当然是找好一个方向 然后尽可能深的搜喽 我们先按照 上 左 下 右 的顺序走走看 01234 0 1 2 3 4 用一颗树来描述一下 伪代码 做道题来试验一下 HDU1010TempteroftheBone ProblemDescriptionThedoggiefoundaboneinanancientmaze whichfascinatedhimalot However whenhepickeditup themazebegantoshake andthedoggiecouldfeelthegroundsinking Herealizedthatthebonewasatrap andhetrieddesperatelytogetoutofthismaze ThemazewasarectanglewithsizesNbyM Therewasadoorinthemaze Atthebeginning thedoorwasclosedanditwouldopenattheT thsecondforashortperiodoftime lessthan1second ThereforethedoggiehadtoarriveatthedooronexactlytheT thsecond Ineverysecond hecouldmoveoneblocktooneoftheupper lower leftandrightneighboringblocks Onceheenteredablock thegroundofthisblockwouldstarttosinkanddisappearinthenextsecond Hecouldnotstayatoneblockformorethanonesecond norcouldhemoveintoavisitedblock Canthepoordoggiesurvive Pleasehelphim 做道题来试验一下 InputTheinputconsistsofmultipletestcases ThefirstlineofeachtestcasecontainsthreeintegersN M andT 1 N M 7 0 T 50 whichdenotethesizesofthemazeandthetimeatwhichthedoorwillopen respectively ThenextNlinesgivethemazelayout witheachlinecontainingMcharacters Acharacterisoneofthefollowing X ablockofwall whichthedoggiecannotenter S thestartpointofthedoggie D theDoor or anemptyblock Theinputisterminatedwiththree0 s Thistestcaseisnottobeprocessed OutputForeachtestcase printinoneline YES ifthedoggiecansurvive or NO otherwise 做道题来试验一下 SampleInput445S X X XD 345S X X D000SampleOutputNOYES 题目大意 有一只小狗在迷宫找到一根骨头 它需要逃出这个迷宫 迷宫里的门只会在特定的时间打开 小狗只有在那时正好到达门才能离开迷宫 迷宫里的地板在站上去1秒后就会塌陷 所以每个位置只能走一次 输入格式 三个数字 分别是迷宫长宽和开门时间S代表小狗现在的位置D代表出口的位置X代表墙 也就是小狗不能走的地方 代表地板输出格式 能 YES 或不能 NO 敲代码呗 悲剧了 为什么会超时 OJ给的时间太少了介个嘛 OJ的测试数据太BT了测试数据太多测试的情况太复杂 搜索本身就很慢本质是穷举盲目性 怎么办 黑掉杭电 修改测试数据和时限 改进我们的程序 似乎不太现实 剪枝 剪枝 目标 消除无意义的搜索 方法 判断当前的搜索是否有意义 无意义则立即返回 例如 题目要求t秒时离开迷宫 迷宫的每个木板只能走一次那么如果木板数小于t小狗必然无法走出迷宫 可以直接免除搜索 奇偶性剪枝 0 0 偶数步1 1 偶数步1 0 奇数步0 1 奇数步 可得 如果n的奇偶性和上表不同 小狗必然无法按时到达出口同样可以免除搜索 把代码改改 A了 DFS就只能走走迷宫 来看一道不是迷宫的搜索题 HDU1016PrimeRingProblem n个数排成一个圆环 要求相邻两个数的和为素数 输入 68输出 Case1 143256165234Case2 12385674125834761476583216743852 DFS一下试试 写代码吧 等一下 DFS递归实现 栈实现 标题好像是 思考一下栈和递归的亲密关系 栈实现DFS的要点 利用栈来记录子节点序列 栈顶元素出栈时将其子节点入栈 不断入栈的过程也就是不断向深处搜索的过程无子节点可入栈的时候进行回溯 举例 树的遍历 练习 HDU 1015 Safecr