BFS迷宫（模板）

解题思路:

                                                                                           利用广度优先搜索（BFS）

  C++ STL queue 模板类（队列）:

queue.push()  元素压入列尾
 
queue.pop()      队首元素出列
 
queue.front()    访问队首元素
 
queue.empty()     若队列为空 return

主要思路：

            需要定义一个上下左右移动的点：

                                                                    dx[4]={0,0,1,-1};   可以自己定义，但是前提是dx与dy的内积必须为0

                                                                    dy[4]={1,-1,0,0};

           BFS函数内中：

            首先是，起点（队首元素）入队（push），队首元素拓展到下一个点，直到队首元素不能够继续拓展就让队首元素出列（pop），再把访问过的格子标记来（vis[i][j]=1）起，并且每次操作步数+1，依次反复循环，直到队列为空（empty）

            在主函数中：

            寻找起点的位置、终点位置的坐标并且记录下来，因为题目是多组输入，所以不要忘记初始化。

参考代码:

#include <bits/stdc++.h>
#include <queue>
#define N 100
using namespace std;
typedef pair< int,int > P;    //用来表示状态坐标 
char mp[N][N];    //地图 
int d[N][N];    //表示所走的步数 
bool vis[N][N];    //标记已经走过的格子 
int dx[]={0,0,1,-1};    //四方向 
int dy[]={1,-1,0,0};    //四方向
int n,m;
int sx,sy;    //起点 
int ex,ey;    //终点
int flag=0;    //判断是否找到了终点 
int BFS()
{
queue <P> que;    //申请队列 
que.push(P(sx,sy));    //把起点加入队列
d[sx][sy]=0;    //并且步数设置为0 
while(!que.empty())    //队列不为空就一直搜 
{
P p=que.front();    //访问队首元素 
if(p.first == ex && p.second == ey)    //如果取出的状态是终点，则搜索结束 
{
flag=1;    //找到了终点标记为1 
break;
}
for(int i=0;i<4;i++)    //往四个方向拓展 
{
int x= p.first + dx[i];
int y= p.second + dy[i];
/*   搜索范围不要超过边界         目标点以及没有被访问过 */ 
if(x>=0 && x<n && y>=0 && y<m && mp[x][y]!='#' && !vis[x][y])
{
vis[x][y]=1;    //标记已经走过 
que.push(P(x,y));    //入队 
d[x][y] = d[p.first][p.second] + 1;    //步数+1 
}
}
que.pop();    //队首元素出列 
}
if(flag==0)    //没有找到终点 
return -1;
else    //找到了终点 
return d[ex][ey];
}
int main()
{
int num;
cin >> num;
while(num--)
{ 
memset(mp,0,sizeof(mp));    //初始化地图 
memset(d,0,sizeof(d));    //初始化地图 
memset(vis,0,sizeof(vis));    //初始化地图
 
cin >> n >> m;
for(int i=0;i<n;i++)
scanf("%s",mp[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(mp[i][j]=='S')    //寻找起点位置 
{
sx=i;//记录起点 
sy=j;
}
if(mp[i][j]=='E')    //寻找终点位置 
{
ex=i;    //记录终点 
ey=j;
}
}
}
int res = BFS();    //调用函数 
cout << res << endl;
flag=0;    //初始化 
}
return 0;
}