ACM算法 BFS.pptx

ACM算法_BFSACM算法系列 之广度优先搜索（Breadth-First-Search）
By : Billy_Hwong
资料取自互联网
2
复习DFS算法
思想： 一直往深处走，直到找到解或者走不下去为止
框架：
Void DFS(dep,…) //dep代表目前DFS的深度
{
if (找到解||走不下去了) // （<- 递归基）
{
…
return;
}
枚举下一种情况，DFS(dep+1,…)
}
例1：POJ 3984
Description
定义一个二维数组： int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 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)
3
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
入口
出口
寻找一条从入口到出口的通路
TIPS：
在迷宫周围加墙，
避免判断是否出界
（Whyyyyyy?)
4
5
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
9
0
9
0
栈
(1,1)
迷宫问题-DFS
6
i
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
9
0
9
0
栈
(1,1)
(2,1)
向下方前进一步
迷宫问题-DFS
7
i
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
9
0
9
0
栈
(1,1)
(2,1)
i
(3,1)
向下方前进一步
迷宫问题-DFS
8
i
i
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
9
0
9
0
栈
(1,1)
(2,1)
(4,1)
(3,1)
i
向下方前进一步
break
迷宫问题-DFS
9
i
i
i
i
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
9
0
9
0
栈
(1,1)
(2,1)
(5,1)
(3,1)
(4,1)
向下方前进一步
break
迷宫问题-DFS
10
i
i
i
i
i
8
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
9
0
9
0
栈
(1,1)
(2,1)
(6,1)
(3,1)
(4,1)
(5,1)
向下方前进一步
break
迷宫问题-DFS