1 #include <iostream> 2 #include <fstream> 3 #include <queue> 4 using namespace std; 5  6 #define MAX_N 100 7 #define MAX_M 100 8  9 const int INF = 100000000;10 11 //pair<int,int>表示坐标状态12 typedef pair<int, int> P;13 14 //输入15 char maze[MAX_N][MAX_M];  //表示迷宫字符串数组16 int N, M;17 int sx, sy;   //起点坐标18 int gx, gy;   //终点坐标19 20 int d[MAX_N][MAX_M];    //到各个位置的作短距离21 22 //4个方向移动的向量23 int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};24 25 26 //求从(sx, sy)到(gx, gy)的最短距离27 //如无法到达，则是INF28 int BFS()29 {30     queue<P> que;31     //把所有位置的距离都初始化为INF32     for (int i = 0; i < N; i++)33         for (int j = 0; j < M; j++)34             d[i][j] = INF;35     //将起点加入队列，并把距离设为036     que.push(P(sx, sy));37     d[sx][sy] = 0;38 39     //不断循环直到队列长度为040     while (que.size())41     {42         P p = que.front(); que.pop();43 44         if (p.first == gx && p.second == gy)45             break;46 47         for (int i = 0; i < 4; i++)48         {49             int nx = p.first + dx[i], ny = p.second + dy[i];50             51             if (0 <= nx && nx < N && 0 <= ny && ny < M && maze[nx][ny] != ‘#‘ && d[nx][ny] == INF)52             {53                 que.push(P(nx, ny));54                 d[nx][ny] = d[p.first][p.second] + 1;55             }56         }57     }58     return d[gx][gy];59 }60 61 int main()62 {63     ifstream cin("input");64 65     cin >> N >> M;66 67     for (int i = 0; i < N; i++)68         for (int j = 0; j < M; j++)69         {70             cin >> maze[i][j];71             if (maze[i][j] == ‘S‘)72             {73                 sx = i;74                 sy = j;75             }76             else if (maze[i][j] == ‘G‘)77             {78                 gx = i;79                 gy = j;80             }81         }82 83     cout << BFS() << endl;84 85     return 0;86 }