ACM-DFS-BFS汇总教学讲解课件

搜索

DFS+BFS剪枝搜索

DFS+BFS剪枝预备知识——树的遍历树的遍历主要有如下四种方法：1.先根/序遍历2.中根/序遍历3.后根/序遍历4.层次遍历分别有什么特点呢？工大ACM团队预备知识——树的遍历树的遍历主要有如下四种方法：分别有什么特2（1）先根遍历对树的访问次序是:1.先访问根结点2.再访问左子树3.最后访问右子树4.对于左右子树的访问也要满足以上规则示例如下：工大ACM团队（1）先根遍历对树的访问次序是:示例如下：工大ACM团队3以上二叉树的先根遍历序列是：？？21357461、2、4、5、3、6、7工大ACM团队以上二叉树的先根遍历序列是：？？21357461、2、4、54（2）中根遍历对树的访问次序是:1.先访问左子树2.再访问根结点3.最后访问右子树4.对于左右子树的访问也要满足以上规则示例如下：工大ACM团队（2）中根遍历对树的访问次序是:示例如下：工大ACM团队5以上二叉树的中根遍历序列是：？？21357464、2、5、1、6、3、7工大ACM团队以上二叉树的中根遍历序列是：？？21357464、2、56（3）后根遍历对树的访问次序是:1.先访问左子树2.再访问右子树3.最后访问根结点4.对于左右子树的访问也要满足以上规则示例如下：工大ACM团队（3）后根遍历对树的访问次序是:示例如下：工大ACM团队7以上二叉树的后根遍历序列是：？？21357464、5、2、6、7、3、1工大ACM团队以上二叉树的后根遍历序列是：？？21357464、5、2、8（4）层次遍历对树的访问次序是:1.先访问根结点2.再访问根结点的子节点（即第二层节点）3.再访问第三层节点4.……示例如下：工大ACM团队（4）层次遍历对树的访问次序是:示例如下：工大ACM团队9以上二叉树的层次遍历序列是：？？21357461、2、3、4、5、6、7工大ACM团队以上二叉树的层次遍历序列是：？？21357461、2、3、10几个基本概念：初始状态：略目标状态：略状态空间：由于求解问题的过程中分枝有很多（主要是求解过程中求解条件的不确定性、不完备性造成的），使得求解的路径很多，这就构成了一个图，我们说这个图就是状态空间。状态空间搜索：就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一条解题的过程，可以从求解的开始到问题的结果。工大ACM团队几个基本概念：初始状态：略工大ACM团队11DFS+BFS深度优先搜索深度优先搜索（DepthFirstSearch）类似于树的先根遍历深搜例子：走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头。广度优先搜索（BreadthFirstSearch）类似于树的按层次遍历的过程广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸远一点的地方……工大ACM团队DFS+BFS深度优先搜索深度优先搜索（DepthFirs12深度优先搜索基本思想从初始状态S开始，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层任一个结点，再检查是否为目标节点G，若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点），当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。若仍不是目标状态，就按该分支一直扩展到叶节点，若仍不是目标，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态，…，一直进行下去，直到找到目标状态G为止。工大ACM团队深度优先搜索基本思想工大ACM团队13搜索过程如下：HALIFBCDEJGKS深度优先搜索示意图工大ACM团队搜索过程如下：HALIFBCDEJGKS深度优先搜索示意图工14广度优先搜索基本思想从初始状态S开始，利用规则，生成所有可能的状态。构成树的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别顺序利用规则。生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。工大ACM团队广度优先搜索基本思想工大ACM团队15搜索过程如下：OPLWVUTRQABCDGEFS广度优先搜索示意图工大ACM团队搜索过程如下：OPLWVUTRQABCDGEFS广度优先搜索16

BFS、DFS算法比较DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。

BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进、出队列。工大ACM团队BFS、DFS算法比较DFS：使用栈保存未被检测的结点，结178123456781234567入口出口迷宫问题-DFS寻找一条从入口到出口的通路工大ACM团队8123456781234567入口出口迷宫问题-DFS寻找18东南迷宫问题(续)北(上)西(左)前进方向：上(北)、下(南)、左(西)、右(东)首先从下方开始，按照逆时针方向搜索下一步可能前进的位置工大ACM团队东南迷宫问题(续)北(上)西(左)前进方向：上(北)、下(南19迷宫问题(续)入口出口在迷宫周围加墙，避免判断是否出界81234567812345679090工大ACM团队迷宫问题(续)入口出口在迷宫周围加墙，避免判断是否出界812208123456781234567迷宫问题(续)9090在寻找出口的过程中，每前进一步，当前位置入栈；每回退一步，栈顶元素出栈栈(1,1)工大ACM团队8123456781234567迷宫问题(续)9090在寻找21i8123456781234567迷宫问题(续)9090栈(1,1)(2,1)向下方前进一步工大ACM团队i8123456781234567迷宫问题(续)9090栈(22i迷宫问题(续)81234567812345679090栈(1,1)(2,1)i(3,1)向下方前进一步工大ACM团队i迷宫问题(续)81234567812345679090栈(23ii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(4,1)(3,1)i向下方前进一步break工大ACM团队ii迷宫问题(续)81234567812345679090栈24iiii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(5,1)(3,1)(4,1)向下方前进一步break工大ACM团队iiii迷宫问题(续)812345678123456790925iiiii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(6,1)(3,1)(4,1)(5,1)向下方前进一步break工大ACM团队iiiii迷宫问题(续)81234567812345679026iiiiii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)向下方前进一步break工大ACM团队iiiiii迷宫问题(续)8123456781234567927iiiiii@迷宫问题(续)81234567812345679090向下方、右方、左方均不能前进，上方是来路，则后退栈(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)break工大ACM团队iiiiii@迷宫问题(续)812345678123456728iiiii@@迷宫问题(续)81234567812345679090栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)向右方、左方均不能前进，下方路不通，上方是来路，则后退break工大ACM团队iiiii@@迷宫问题(续)812345678123456729iiiii@@81234567迷宫问题(续)0981234567812345679090栈(1,1)(2,1)(3,1)(4,1)(5,1)(5,2)向右方前进一步break工大ACM团队iiiii@@81234567迷宫问题(续)0981234530iiiiii@@迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(5,3)(5,2)break工大ACM团队iiiiii@@迷宫问题(续)81234567812345631iiiiiii@@81234567迷宫问题(续)0981234567812345679090向下方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(5,2)(5,3)break工大ACM团队iiiiiii@@81234567迷宫问题(续)09812332iiiiiii@@迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,4)(5,2)(5,3)(6,3)ibreak工大ACM团队iiiiiii@@迷宫问题(续)8123456781234533iiiiiii@ii@迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,5)(5,2)(5,3)(6,3)(6,4)break工大ACM团队iiiiiii@ii@迷宫问题(续)81234567812334iiiiiii@iii@81234567迷宫问题(续)0981234567812345679090向下方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(7,5)(5,2)(5,3)(6,3)(6,4)(6,5)break工大ACM团队iiiiiii@iii@81234567迷宫问题(续)09835iiiiiii@iii@i迷宫问题(续)81234567812345679090向下方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,5)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)break工大ACM团队iiiiiii@iii@i迷宫问题(续)812345678136iiiiiii@iii@ii迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,6)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)break工大ACM团队iiiiiii@iii@ii迷宫问题(续)81234567837iiiiiii@iii@iii迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,7)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)break工大ACM团队iiiiiii@iii@iii迷宫问题(续)8123456738iiiiiii@iii@ii迷宫问题(续)81234567812345679090下方路不通，向右方前进一步，到达出口栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,8)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)ii(8,7)break工大ACM团队iiiiiii@iii@ii迷宫问题(续)81234567839iiiiiii@iii@iiii81234567迷宫问题(续)981234567090用栈保存了路径栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,8)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)(8,7)工大ACM团队iiiiiii@iii@iiii81234567迷宫问题(续40迷宫问题(最短路径)-BFS入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队迷宫问题(最短路径)-BFS入口出口借助于队列可求得入口到出4111迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队11迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的421122迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队1122迷宫问题(最短路径)入口出口借助于队列可求得入口到出43112233迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队112233迷宫问题(最短路径)入口出口借助于队列可求得入口4411223434迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队11223434迷宫问题(最短路径)入口出口借助于队列可求得4511223453455迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队11223453455迷宫问题(最短路径)入口出口借助于队列4611262345345656迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队11262345345656迷宫问题(最短路径)入口出口借助4717126723453456576迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队17126723453456576迷宫问题(最短路径)入口出4817812678234534565786迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队17812678234534565786迷宫问题(最短路径)491789126782345345657896迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队1789126782345345657896迷宫问题(最短路50178912678234510310456105789610迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队178912678234510310456105789610511789126782345101131110114561011578961011迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队1789126782345101131110114561015217891267812234510113111011124561011125789610121112迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队178912678122345101131110111245531789131267812234510113111011124561011121357896101312111213迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队178913126781223451011311101112541789131267812234510113111011124561011121357896101312111213迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队17891312678122345101131110111255小结 广度和深度优先搜索有一个很大的缺陷,就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。

所以，在这里再次强调“剪枝”！剪枝：通过某种判断，避免一些不必要的遍历过程，形象的说剪去了搜索树中的某些“枝条”。工大ACM团队小结 广度和深度优先搜索有一个很大的缺陷,就是他们都是56HDOJ_1010TempteroftheBone

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工大ACM团队HDOJ_1010TempteroftheBon57HDOJ_1010TempteroftheBone

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工大ACM团队HDOJ_1010TempteroftheBon58HDOJ_1010TempteroftheBone

OutputForeachtestcase,printinoneline"YES"ifthedoggiecansurvive,or"NO"otherwise.工大ACM团队HDOJ_1010TempteroftheBon59HDOJ_1010TempteroftheBone

SampleInput445S.X...X...XD....345S.X...X....D000工大ACM团队HDOJ_1010TempteroftheBon60HDOJ_1010TempteroftheBone

SampleOutputNOYES工大ACM团队HDOJ_1010TempteroftheBon61要点分析：典型的迷宫搜索，做出该题将具有里程碑式的意义！能不能枚举出所有抵达方案，再在通过检查时间时间是否吻合，得到结果，用DFS进行搜索。DFS搜索完成后，发现超时，得剪枝才行。工大ACM团队要点分析：典型的迷宫搜索，做出该题将具有里程碑式的意义！工大62想到了什么剪枝条件？每个block只能走一次要求恰好某个给定的时间到达出口如果可走的block的总数小于时间，将会产生什么情况？还想到什么剪枝？工大ACM团队想到了什么剪枝条件？每个block只能走一次还想到什么剪枝？63奇偶性剪枝可以把map看成这样：010101101010010101101010010101从为0的格子走一步，必然走向为1的格子从为1的格子走一步，必然走向为0的格子即：

0->1或1->0必然是奇数步

0->0走1->1必然是偶数步所以当遇到从0走向0但是要求时间是奇数的，或者，从1走向0但是要求时间是偶数的都可以直接判断不可达！结论：工大ACM团队奇偶性剪枝可以把map看成这样：结论：工大ACM团队64奇偶性剪枝那么设所在位置(x,y)与目标位置(dx,dy)如果abs(dx-x)+abs(dy-y)为偶数，则说明abs(dx-x)+和abs(dy-y)的奇偶性相同，需要走偶数步如果abs(dx-x)+abs(dy-y)为奇数，那么说明abs(dx-x)和abs(dy-y)的奇偶性不同，需要走奇数步解为abs(dx-sx)+abs(dy-sy)的奇偶性就确定了所需要的步数的奇偶性！！而(ti-setp)表示剩下还需要走的步数，由于题目要求要在ti时恰好到达，那么(ti-step)与abs(x-y)+abs(dx-dy)的奇偶性必须相同因此temp=ti-step-abs(dx-x)-abs(dy-y)必然为偶数！工大ACM团队奇偶性剪枝那么设所在位置(x,y)与目标位置(dx,65核心代码voidDfsSerch(intx,inty,intstep){inttemp;temp=ti-step-abs(dx-x)-abs(dy-y);if(temp<0||temp%2==1)return;inttx,ty;for(inti=0;i<4;i++)//四个方向探索上下左右走{tx=x+dir[i][0];ty=y+dir[i][1];if(a[tx][ty]=='D'&&step==ti-1){flag=1;return;}if(a[tx][ty]=='.'&&(tx>=0&&tx<n)&&(ty>=0&&ty<m)){a[tx][ty]='X';//标记访问

DfsSerch(tx,ty,step+1);a[tx][ty]='.';//回溯取消标记

if(flag==1)return;//找到直接返回

}}}工大ACM团队核心代码voidDfsSerch(intx,inty,66附录：推荐搜索题：HDOJ1010、1240、1241、12421072、1253、1312、1372(以上题目类似于1010)1238、1239、1015、10161401、1515、1548工大ACM团队附录：推荐搜索题：HDOJ1010、1240、1241、1267DFSzju1711《SumItUp》zju1004《AnagramsbyStack》zju1204《Additiveequations》zju1984《GeneticCode》zju1457《PrimeRingProblem》zju1008《GnomeTetravex》zju1411《Anniversary》zju1267《MappingtheRoute》zju1482《Partitions》zju1990《SubwayTreeSystems》工大ACM团队DFSzju1711《SumItUp》工大ACM团队68BFSzju1091《KnightMoves》zju1047《ImagePerimeters》zju1103《HikeonaGraph》zju1649《Rescue》zju1310《Robot》zju1136《Multiple》zju1530《FindTheMultiple》zju1301《TheNewVilla》工大ACM团队BFSzju1091《KnightMoves》工大ACM69加油!加油!搜索

DFS+BFS剪枝搜索

DFS+BFS剪枝预备知识——树的遍历树的遍历主要有如下四种方法：1.先根/序遍历2.中根/序遍历3.后根/序遍历4.层次遍历分别有什么特点呢？工大ACM团队预备知识——树的遍历树的遍历主要有如下四种方法：分别有什么特72（1）先根遍历对树的访问次序是:1.先访问根结点2.再访问左子树3.最后访问右子树4.对于左右子树的访问也要满足以上规则示例如下：工大ACM团队（1）先根遍历对树的访问次序是:示例如下：工大ACM团队73以上二叉树的先根遍历序列是：？？21357461、2、4、5、3、6、7工大ACM团队以上二叉树的先根遍历序列是：？？21357461、2、4、574（2）中根遍历对树的访问次序是:1.先访问左子树2.再访问根结点3.最后访问右子树4.对于左右子树的访问也要满足以上规则示例如下：工大ACM团队（2）中根遍历对树的访问次序是:示例如下：工大ACM团队75以上二叉树的中根遍历序列是：？？21357464、2、5、1、6、3、7工大ACM团队以上二叉树的中根遍历序列是：？？21357464、2、576（3）后根遍历对树的访问次序是:1.先访问左子树2.再访问右子树3.最后访问根结点4.对于左右子树的访问也要满足以上规则示例如下：工大ACM团队（3）后根遍历对树的访问次序是:示例如下：工大ACM团队77以上二叉树的后根遍历序列是：？？21357464、5、2、6、7、3、1工大ACM团队以上二叉树的后根遍历序列是：？？21357464、5、2、78（4）层次遍历对树的访问次序是:1.先访问根结点2.再访问根结点的子节点（即第二层节点）3.再访问第三层节点4.……示例如下：工大ACM团队（4）层次遍历对树的访问次序是:示例如下：工大ACM团队79以上二叉树的层次遍历序列是：？？21357461、2、3、4、5、6、7工大ACM团队以上二叉树的层次遍历序列是：？？21357461、2、3、80几个基本概念：初始状态：略目标状态：略状态空间：由于求解问题的过程中分枝有很多（主要是求解过程中求解条件的不确定性、不完备性造成的），使得求解的路径很多，这就构成了一个图，我们说这个图就是状态空间。状态空间搜索：就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，就是在解一个问题时，找到一条解题的过程，可以从求解的开始到问题的结果。工大ACM团队几个基本概念：初始状态：略工大ACM团队81DFS+BFS深度优先搜索深度优先搜索（DepthFirstSearch）类似于树的先根遍历深搜例子：走迷宫，你没有办法用分身术来站在每个走过的位置。不撞南山不回头。广度优先搜索（BreadthFirstSearch）类似于树的按层次遍历的过程广搜例子:你的眼镜掉在地上以后，你趴在地板上找。你总是先摸最接近你的地方，如果没有，再摸远一点的地方……工大ACM团队DFS+BFS深度优先搜索深度优先搜索（DepthFirs82深度优先搜索基本思想从初始状态S开始，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层任一个结点，再检查是否为目标节点G，若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点），当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。若仍不是目标状态，就按该分支一直扩展到叶节点，若仍不是目标，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态，…，一直进行下去，直到找到目标状态G为止。工大ACM团队深度优先搜索基本思想工大ACM团队83搜索过程如下：HALIFBCDEJGKS深度优先搜索示意图工大ACM团队搜索过程如下：HALIFBCDEJGKS深度优先搜索示意图工84广度优先搜索基本思想从初始状态S开始，利用规则，生成所有可能的状态。构成树的下一层节点，检查是否出现目标状态G，若未出现，就对该层所有状态节点，分别顺序利用规则。生成再下一层的所有状态节点，对这一层的所有状态节点检查是否出现G，若未出现，继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。工大ACM团队广度优先搜索基本思想工大ACM团队85搜索过程如下：OPLWVUTRQABCDGEFS广度优先搜索示意图工大ACM团队搜索过程如下：OPLWVUTRQABCDGEFS广度优先搜索86

BFS、DFS算法比较DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。

BFS：使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进、出队列。工大ACM团队BFS、DFS算法比较DFS：使用栈保存未被检测的结点，结878123456781234567入口出口迷宫问题-DFS寻找一条从入口到出口的通路工大ACM团队8123456781234567入口出口迷宫问题-DFS寻找88东南迷宫问题(续)北(上)西(左)前进方向：上(北)、下(南)、左(西)、右(东)首先从下方开始，按照逆时针方向搜索下一步可能前进的位置工大ACM团队东南迷宫问题(续)北(上)西(左)前进方向：上(北)、下(南89迷宫问题(续)入口出口在迷宫周围加墙，避免判断是否出界81234567812345679090工大ACM团队迷宫问题(续)入口出口在迷宫周围加墙，避免判断是否出界812908123456781234567迷宫问题(续)9090在寻找出口的过程中，每前进一步，当前位置入栈；每回退一步，栈顶元素出栈栈(1,1)工大ACM团队8123456781234567迷宫问题(续)9090在寻找91i8123456781234567迷宫问题(续)9090栈(1,1)(2,1)向下方前进一步工大ACM团队i8123456781234567迷宫问题(续)9090栈(92i迷宫问题(续)81234567812345679090栈(1,1)(2,1)i(3,1)向下方前进一步工大ACM团队i迷宫问题(续)81234567812345679090栈(93ii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(4,1)(3,1)i向下方前进一步break工大ACM团队ii迷宫问题(续)81234567812345679090栈94iiii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(5,1)(3,1)(4,1)向下方前进一步break工大ACM团队iiii迷宫问题(续)812345678123456790995iiiii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(6,1)(3,1)(4,1)(5,1)向下方前进一步break工大ACM团队iiiii迷宫问题(续)81234567812345679096iiiiii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)向下方前进一步break工大ACM团队iiiiii迷宫问题(续)8123456781234567997iiiiii@迷宫问题(续)81234567812345679090向下方、右方、左方均不能前进，上方是来路，则后退栈(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)break工大ACM团队iiiiii@迷宫问题(续)812345678123456798iiiii@@迷宫问题(续)81234567812345679090栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)向右方、左方均不能前进，下方路不通，上方是来路，则后退break工大ACM团队iiiii@@迷宫问题(续)812345678123456799iiiii@@81234567迷宫问题(续)0981234567812345679090栈(1,1)(2,1)(3,1)(4,1)(5,1)(5,2)向右方前进一步break工大ACM团队iiiii@@81234567迷宫问题(续)09812345100iiiiii@@迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(5,3)(5,2)break工大ACM团队iiiiii@@迷宫问题(续)812345678123456101iiiiiii@@81234567迷宫问题(续)0981234567812345679090向下方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(5,2)(5,3)break工大ACM团队iiiiiii@@81234567迷宫问题(续)098123102iiiiiii@@迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,4)(5,2)(5,3)(6,3)ibreak工大ACM团队iiiiiii@@迷宫问题(续)81234567812345103iiiiiii@ii@迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,5)(5,2)(5,3)(6,3)(6,4)break工大ACM团队iiiiiii@ii@迷宫问题(续)812345678123104iiiiiii@iii@81234567迷宫问题(续)0981234567812345679090向下方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(7,5)(5,2)(5,3)(6,3)(6,4)(6,5)break工大ACM团队iiiiiii@iii@81234567迷宫问题(续)098105iiiiiii@iii@i迷宫问题(续)81234567812345679090向下方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,5)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)break工大ACM团队iiiiiii@iii@i迷宫问题(续)8123456781106iiiiiii@iii@ii迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,6)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)break工大ACM团队iiiiiii@iii@ii迷宫问题(续)812345678107iiiiiii@iii@iii迷宫问题(续)81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,7)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)break工大ACM团队iiiiiii@iii@iii迷宫问题(续)81234567108iiiiiii@iii@ii迷宫问题(续)81234567812345679090下方路不通，向右方前进一步，到达出口栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,8)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)ii(8,7)break工大ACM团队iiiiiii@iii@ii迷宫问题(续)812345678109iiiiiii@iii@iiii81234567迷宫问题(续)981234567090用栈保存了路径栈(1,1)(2,1)(3,1)(4,1)(5,1)(8,8)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)(8,7)工大ACM团队iiiiiii@iii@iiii81234567迷宫问题(续110迷宫问题(最短路径)-BFS入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队迷宫问题(最短路径)-BFS入口出口借助于队列可求得入口到出11111迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队11迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的1121122迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队1122迷宫问题(最短路径)入口出口借助于队列可求得入口到出113112233迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队112233迷宫问题(最短路径)入口出口借助于队列可求得入口11411223434迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队11223434迷宫问题(最短路径)入口出口借助于队列可求得11511223453455迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队11223453455迷宫问题(最短路径)入口出口借助于队列11611262345345656迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队11262345345656迷宫问题(最短路径)入口出口借助11717126723453456576迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队17126723453456576迷宫问题(最短路径)入口出11817812678234534565786迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)81234567812345679090工大ACM团队17812678234534565786迷宫问题(最短路径)1191789126782345345657896迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队1789126782345345657896迷宫问题(最短路120178912678234510310456105789610迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队1789126782345103104561057896101211789126782345101131110114561011578961011迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队17891267823451011311101145610112217891267812234510113111011124561011125789610121112迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队1789126781223451011311101112451231789131267812234510113111011124561011121357896101312111213迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队1789131267812234510113111011121241789131267812234510113111011124561011121357896101312111213迷宫问题(最短路径)入口出口借助于队列可求得入口到出口的最短路径(若存在)812345678123456790909工大ACM团队178913126781223451011311101112125小结 广度和深度优先搜索有一个很大的缺陷,就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。

所以，在这里再次强调“剪枝”！剪枝：通过某种判断，避免一些不必要的遍历过程，形象的说剪去了搜索树中的某些“枝条”。工大ACM团队小结 广度和深度优先搜索有一个很大的缺陷,就是他们都是126HDOJ_1010TempteroftheBone

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工大ACM团队HDOJ_1010TempteroftheBon127HDOJ_1010TempteroftheBone

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工大ACM团队HDOJ_1010TempteroftheBon128HDOJ_1010Temptero