我们用一个二维的字符数组来表示迷宫；其中字符 S 表示起点，字符 T 表示终点，字符 * 表示墙壁，字符 . 表示平地。你需要从S出发走到T，每次只能向上下左右相邻的位置移动，不能走出地图，也不能穿过墙壁，每个点只能通过一次。你需要编程来求解出一种从起点到终点路程最短走法。无法到达终点输出-1；
输入的第一行为两个整数，表示迷宫的行数和列数，中间用空格分开。下面每行为迷宫每行的样子。
样例输入：
5 6 ....S* .**... .*..*. *..**. .T....
样例输出：
7
#include <iostream> #include <queue> //队列，STL队列库，先进先出类型 using namespace std; int n,m; char a[105][105]; int b[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; //迷宫上左下右四个方向移动 bool c[105][105]; //记录有无过进入队列 bool in(int x,int y){ return x>=0 && x<n && y>=0 && y<m; } struct node{ //定义结构体node，x，y代表位置，d代表步数 int x,y,d; node(int xx,int yy,int dd){ x=xx; //结构体构造函数，便于赋值 y=yy; d=dd; } }; int bfs(int x,int y){ queue<node> now; //定义一个队列，内部时node类型的结构体 c[x][y]=1; now.push(node(x,y,0)); //进入队列 while(!now.empty()){ //当队列为空时结束循环 node dange=now.front(); //得到队首 now.pop(); //弹出队首 for(int i=0;i<4;i++){ int tx=dange.x+b[i][0]; int ty=dange.y+b[i][1]; //四个方向移动； if(in(tx,ty)&&a[tx][ty]!='*'&&!c[tx][ty]){ //判断是否可以移动 if(a[tx][ty]=='T'){ return dange.d+1; //如果到达终点返回步数 }else{ c[tx][ty]=1; //没有到达终点，把四个方向（可行的）加入队列 now.push(node(tx,ty,dange.d+1)); } } } } return -1; } int main(){ int qx,qy; cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>a[i][j]; } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]=='S'){ qx=i; qy=j; } } } cout<<bfs(qx,qy); return 0; }
BFS广度优先搜索，每次优先搜索最近的节点，与DFS一条路走到黑形成鲜明对比。
