迷宫的最短路径
问题描述
给定一个大小为N×M的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四个的通道移动。请求出从起点到终点所需的最小步数。请注意，本题假定从起点一定可以移动到终点。（N,M≤100）
（‘#’, ‘.’ , ‘S’, 'G’分别表示墙壁、通道、起点和终点）
样例输入：
10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
样例输出：
22
—— 分割线 ——
分析：
首先说明，本题其实是在为蓝桥杯 算法提高 学霸的迷宫这道题做一个铺垫
这道题放在《算法与数据结构》专栏里面是因为其实这是一个很很很很经典的迷宫问题，前面的概论只是介绍了BFS（还有DFS）的原理，但是毕竟实践才是检验真理的唯一标准。而这道题，个人感觉是任何想要深入了解搜索算法的人的必修课（也是所有初学者必须看的第一题）。
我相信当你在解决了这个问题之后，将会对广度优先搜索算法有一个十分深刻的认识，并且之后对于那些涉及到迷宫问题或者说图的遍历问题时，你将更加的熟练
废话不多说，直接开整！！！
变量声明：len[x][y]表示从图的起点到坐标为x,y的点的距离。
解决迷宫问题的大致思路如下：
① 从起点开始，将当前点加入队列，并设置len[start_x][start_y]为0
② 先进入一个判断队列是否为空的while循环，然后再从队列首端取出元素p（即队列中的第一个点）
③ 接着再进入一个for循环，该循环用来遍历当前点的四个移动方向是否合法，合法的我们标记该位置为已走，并且把len[该点x][该点y]=len[p.x][p.y]+1，最终在将要退出for循环前，判断该点坐标是否等于出口坐标，是则退出循环输出结果，否则就把这个当前点添加进队列，然后再进行下一次循环
④ 当四次循环都结束后（即四个方向走走遍后），转②（前提是上面的循环是正常退出的，即i==4）。否则就表示找到了出口，由于这是深度优先，是一级一级走的，故当找到终点时，当前步数一定会是最短的。
注：其实上面第3步的目的就是把每个可前进点都放进队列中，并且统计好该点的距离信息，然后对于while循环而言，下一次取出的p点就是之前走过的某个点了，你又进行下面的步骤其实就是在不断的发散该点可能的途径，就像在宽度优先搜索的图论介绍中的“分身”概念。然后这个被取出的p点不断的更换不断的发散，最后总能到达目的地（如果存在）
下面给出本题的完整代码：
—— 分割线 ——
#include<iostream>
#include<queue>
using namespace std;
const int MAX_X=105,MAX_Y=105; //图的最大规格
const int INF=1000000; //预设一个很大的不会取到或出现的值来作为未走过的标记
char map[MAX_X][MAX_Y]; //图
int n,m; //对某次而言的规格
int start_x,start_y; //起始地点（入口）
int goal_x,goal_y; //目标地点（出口）
int len[MAX_X][MAX_Y]; //len[x][y]的含义：入口到坐标为x,y的点的距离
int move[4][2]={{1,0},{0,-1},{0,1},{-1,0}};//视为向量（以(0,0)点为出发点）四种移动方式分别是{'D','L','R','U'}
struct Point{ //结构体（点的抽象实现）
int x,y;
Point(int a,int b){ x=a,y=b; }
};
void bfs()
{
queue<Point> q;
for(int i=0;i<n;i++) // 初始化所有的点为未走过
{
for(int j=0;j<m;j++)
len[i][j]=INF;
}
q.push(Point(start_x,start_y));
len[start_x][start_y]=0; //入口标记为0，表示已经走过了
while(!q.empty()) //题目保证有终点，故可以这么设置循环条件
{
Point p=q.front();q.pop(); //取第一个队列元素进行发散，并将其推出
int i;
for(i=0;i<4;i++) //分别判断四种行走方式
{
int new_x=p.x+ move[i][0];
int new_y=p.y+ move[i][1];
if(new_x>=0&&new_x<n&&new_y>=0&&new_y<m //判断未出边界
&&map[new_x][new_y]!='#'&&len[new_x][new_y]==INF)//判断可移动并且未走过
{
q.push(Point(new_x,new_y)); //入队列
len[new_x][new_y]=len[p.x][p.y]+ 1; //赋值为前一个路程长度加1
if(new_x==goal_x && new_y==goal_y) break;//如果已经到了终点则直接退出循环
}
}
if(i!=4) break; //对于上面的退出作是否是非法退出的判断，是则表示找到了出口，直接退出全过程
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>map[i];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(map[i][j]=='S')
start_x=i,start_y=j;
if(map[i][j]=='G')
goal_x=i,goal_y=j;
}
bfs();
cout<<len[goal_x][goal_y]<<endl;
return 0;
}
