利用宽度优先搜索解决迷宫最短路径问题
题目：给定一个大小为N*M的迷宫，迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格的通道移动。求从起点到终点所需最小步数。
注意：本题假定从起点一定可以移动到终点。
限制条件
N，M<=100
(# . S G 分别表示墙壁，通道，起点和终点）
代码语言：javascript复制#include<iostream>
#include<queue>
using namespace std;
const int INF=100000000;
const int MAX_M=100,MAX_N=100 ;
typedef pair<int,int>P;
char maze[MAX_N][MAX_M 1];//迷宫
int N,M;
int sx,sy;//起点坐标
int gx,gy;//终点坐标
int d[MAX_N][MAX_M];//到各个位置最短距离的数组
//4个方向移动的向量
int dx[4]= {1,0,-1,0},dy[4]= {0,1,0,-1};
//求从（sx,sy）到（gx,gy)的最短距离
//如果无法到达，则是INF
int bfs()
{
queue<P>que;
//把所有的位置都初始化为INF
for(int i=0; i<N; i )
{
for(int j=0; j<M; j )
{
d[i][j]=INF;
}
}
//将起点加入队列，并把 这一地点的距离设置为0
que.push(P(sx,sy));
d[sx][sy]=0;
//不断循环知道队列的长度为0
while(que.size())
{
//从队列的最前端取出元素
P p=que.front();
que.pop();
//如果取出的状态已经是终点，则结束搜索
if(p.first==gx&&p.second==gy)
break;
for(int i=0; i<4; i )
{
//移动之后的位置记为（nx,ny）
int nx=p.first dx[i],ny=p.second dy[i];
//判断是否可以移动以及是否已经访问过（d[nx][ny]!=INF即为已访问过
if(nx>=0&&nx<N&&ny>=0&&ny<M&&maze[nx][ny]!='#'&&d[nx][ny]==INF)
{
//可以移动的话，则加入到队列，并且到该位置的距离确定为到p的距离 1
que.push(P(nx,ny));
d[nx][ny]=d[p.first][p.second] 1;
}
}
}
return d[gx][gy];
}
void solve()
{
int res=bfs();
cout<<res<<endl;
}
int main()
{
cin>>N>>M;
for(int i=0; i<N; i )
{
for(int j=0; j<M; j )
{
cin>>maze[i][j];
if(maze[i][j]=='S')
sx=i,sy=j;
if(maze[i][j]=='G')
gx=i,gy=j;//注意if 等条件语句中如果不适用大括号，
}//那么必须中间是逗号，否则if语句的约束只到第一个分号处。
}
solve();
return 0;
}
//输入
//10 10
//#S######.#
//......#..#
//.#.##.##.#
//.#........
//##.##.####
//....#....#
//.#######.#
//....#.....
//.####.###.
//....#...G#题目来自《挑战程序设计竞赛》
