迷宫的最短路径(bfs)

宽度优先搜索（BFS，Breadth-First Search）也是搜索的手段之一，与深度优先搜索类似，从某个状态出发搜索所有可以到达的状态。

与深度优先搜索的不同之处在于搜索的顺序，宽度优先搜索总是先搜索距离初始状态最近的状态。也就是说，它是按照开始状态→只需一次转移就能到达的所有状态→只需2次就可以到达的所有状态→…按照这样的顺序进行搜索。对于同一个状态，宽度优先搜索只经过一次，因此时间复杂度为O（状态数×转移的方式）。

深度优先搜索利用了栈进行计算，而宽度优先搜索则利用了队列进行计算。搜索时首先将状态添加进队列里，此后从队列的最前端不断取出状态，把从该状态可以转移到的状态尚未访问过的部分加入到队列中，如此往复，直至队列被取空或找到了问题的解。通过观察这个队列，我们就可以知道所有的状态都是按照距初始状态由近及远的顺序遍历的。

例题：

迷宫的最短路径

　　给定一个大小为N×M的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四个的通道移动。请求出从起点到终点所需的最小步数。请注意，本题假定从起点一定可以移动到终点。（N,M≤100）（'#', '.' , 'S', 'G'分别表示墙壁、通道、起点和终点）

输入：

10 10

#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

输出：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <queue>
 6 #define N 105
 7 #define inf 1000000000
 8 using namespace std;
 9 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
10 char k[N][N];
11 int vis[N][N];
12 int n,m;
13 int px,py,nx,ny;
14 typedef pair<int,int> p;
15 queue<p> q;
16 int bfs(){
17   while(q.size()){
18     p r=q.front();q.pop();
19     if(r.first==nx&&r.second==ny){
20       break;
21     }
22     for(int i=0;i<4;i++){
23       int xx=r.first+dir[i][0];
24       int yy=r.second+dir[i][1];
25       if(xx>=0&&xx<=n&&yy>=0&&yy<=m&&k[xx][yy]!='#'&&vis[xx][yy]==inf){
26         q.push(p(xx,yy));
27         vis[xx][yy]=vis[r.first][r.second]+1;
28     }
29   }
30 }
31 return vis[nx][ny];
32 }
33 int main(){
34   cin>>n>>m;
35   for(int i=0;i<n;i++)
36     for(int j=0;j<m;j++)
37       vis[i][j]=inf;
38   for(int i=0;i<n;i++)
39     for(int j=0;j<m;j++){
40       cin>>k[i][j];
41       if(k[i][j]=='S')
42         px=i,py=j;
43       if(k[i][j]=='G')
44         nx=i,ny=j;
45     }
46   q.push(p(px,py));
47   vis[px][py]=0;
48   printf("%d
",bfs());
49   return 0;
50 }