《挑战程序设计竞赛》例题：迷宫的最短路径

例题大意：给一个NM的迷宫，输入NM个字符，其中'#'代表墙壁，'.'代表道路，'S'代表起点，'G'代表终点，求到达'G'的最小步数
分析：求最短路径或者最少操作之类的题一般用广度优先搜索（BFS），BFS利用队列，先进先出，先将起始点放入队列中，如果下一地方能走的话更新一下队列起始的状态并且记录下到达这一位置的最少步数，到达终点或者死胡同（如果到达死胡同那么队列无法增加数据那么会终止循环）

#include <bits/stdc++.h>
using namespace std;
#define max_n 100
int M,N,start1,start2,end1,end2;//纪律起始坐标与终点坐标的变量
int move_x[4]={0,-1,1,0},move_y[4]={-1,0,0,1};//进行四个方向的移动
char pass[max_n][max_n];//地形数组
typedef pair<int,int> p;//将某点坐标x,y联系在一起
int s[max_n][max_n];
int bfs(int x,int y)
{
    queue<p> t;//队列
    s[x][y]=0;//先将起始点赋值为0，代表到达这一点的步数为0
    t.push(p(x,y));//将起始点放入队列之中
    while(t.size())
    {
        p h=t.front();//获得队列的起始数据
        t.pop();//删除起始数据,到时候如果进了死胡同通过这个使队列大小变为0
        for(int i=0;i<4;i++)
        {
            int a=h.first+move_x[i],b=h.second+move_y[i];//进行移动后的坐标（第二次写时，这里出了大问题，h.first和h.second我用x,y写了，所以一直出错）
            if(a>=0&&a<N&&b>=0&&b<M&&s[a][b]==-1&&pass[a][b]!='#')//约束条件
            {
                t.push(p(a,b));//如果上述条件满足，那么将它增加到队列之中，使得队列大小不为0
                s[a][b]=s[h.first][h.second]+1;//到达该位置的最短步数，能够到这里进行赋值的肯定是最先到达这里的，所以是最短步数
            }
        }
    }
    return s[end1][end2];

}
int main()
{
   cin>>M>>N;
   for(int i=0;i<M;i++)
   {
       for(int m=0;m<N;m++)
       {
           cin>>pass[i][m];
           if(pass[i][m]=='S')
           {
               start1=i;
               start2=m;
           }
           if(pass[i][m]=='G')
           {
               end1=i;
               end2=m;
           }
       }
   }
   for(int i=0;i<M;i++)
   {
       for(int m=0;m<N;m++)
       {
           s[i][m]=-1;//将步数都赋值为-1，如果不为-1说明有人走过了
       }
   }
   cout<<bfs(start1,start2);

}

一组测试数据
输入：
10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

输出22