资源描述：
《ACM算法_BFS.pptx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ACM算法系列之广度优先搜索（Breadth-First-Search）By:Billy_Hwong资料取自互联网2复习DFS算法思想：一直往深处走，直到找到解或者走不下去为止框架：VoidDFS(dep,…)//dep代表目前DFS的深度{if(找到解
2、
3、走不下去了)//（<-递归基）{…return;}枚举下一种情况，DFS(dep+1,…)}例1：POJ3984Description定义一个二维数组：intmaze[5][5]={ 0,1,0,0,0, 0,1,0,1,0, 0,0,0,0
4、,0, 0,1,1,1,0, 0,0,0,1,0, };它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。Output左上角到右下角的最短路径，格式如样例所示。(0,0)(1,0)(2,0)(2,1)(2,2)(2,3)(2,4)(3,4)(4,4)8123456781234567入口出口寻找一条从入口到出口的通路TIPS：在迷宫周围加墙，避免判断是否出界（Whyyyyyy?)581234567812345679090栈
5、(1,1)迷宫问题-DFS6i81234567812345679090栈(1,1)(2,1)向下方前进一步迷宫问题-DFS7i81234567812345679090栈(1,1)(2,1)i(3,1)向下方前进一步迷宫问题-DFS8ii81234567812345679090栈(1,1)(2,1)(4,1)(3,1)i向下方前进一步break迷宫问题-DFS9iiii81234567812345679090栈(1,1)(2,1)(5,1)(3,1)(4,1)向下方前进一步break迷宫问题-DF
6、S10iiiii81234567812345679090栈(1,1)(2,1)(6,1)(3,1)(4,1)(5,1)向下方前进一步break迷宫问题-DFS11iiiiii迷宫问题(续)81234567812345679090栈(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1)向下方前进一步break12iiiiii@81234567812345679090向下方、右方、左方均不能前进，上方是来路，则后退栈(1,1)(2,1)(7,1)(3,1)(4,1)(5,1)(6,1
7、)break迷宫问题-DFS13iiiii@@81234567812345679090栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)向右方、左方均不能前进，下方路不通，上方是来路，则后退break迷宫问题-DFS14iiiii@@812345670981234567812345679090栈(1,1)(2,1)(3,1)(4,1)(5,1)(5,2)向右方前进一步break迷宫问题-DFS15iiiiii@@81234567812345679090下方路不通，向右方前进一步栈(1
8、,1)(2,1)(3,1)(4,1)(5,1)(5,3)(5,2)break迷宫问题-DFS16iiiiiii@@812345670981234567812345679090向下方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,1)(5,2)(5,3)break迷宫问题-DFS17iiiiiii@@81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,4)(5,2)(5,3)(6,3)ibreak迷宫问题-D
9、FS18iiiiiii@ii@81234567812345679090下方路不通，向右方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(6,5)(5,2)(5,3)(6,3)(6,4)break迷宫问题-DFS19iiiiiii@iii@812345670981234567812345679090向下方前进一步栈(1,1)(2,1)(3,1)(4,1)(5,1)(7,5)(5,2)(5,3)(6,3)(6,4)(6,5)break迷宫问题-DFS20iiiiiii@iii@i812
10、34567812345679090向下方前进一步栈(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迷宫问题-DFS21iiiiiii@iii@ii81234567812345679090下方路不通，向右方前进一步栈(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迷宫问题-DFS22iiiiiii@iii@iii8123456
