资源描述:
《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