小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。
输入
输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：
‘S’：起点
‘E’：终点
‘-’：空地，可以通过
‘#’：障碍，无法通过
输入数据保证有且仅有一个起点和终点。
输出
对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。
样例输入 复制
1
5 5
S-###
##---
E#---
---##
样例输出 复制
9
```c++
#include<iostream>
#include<vector>
using namespace std;
const int MAX=10;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
char mg[MAX][MAX]={};
int cnt=0,M,N,T;
class Box
{
public:
int i;
int j;
Box(int i1,int j1):i(i1),j(j1){}
};
void mgpath(int xi,int yi,int xe,int ye,vector<Box> path)
{
Box b(xi,yi);
path.push_back(b);
mg[xi][yi]='#';
if(xi==xe&&yi==ye)
{
cnt++;
for(int k=0;k<path.size();k++)
printf("(%d,%d)",path[k].i,path[k].j);
cout<<endl;
mg[xi][yi]='-';
}
else
{
int di=0;
while(di<4)
{
int i=xi+dx[di];
int j=yi+dy[di];
if(i>=0&&i<M&&j>=0&&j<N&&mg[xi][yi]=='-')
mgpath(i,j,xe,ye,path);
di++;
}
mg[xi][yi]='-';
}
}
int main()
{
cin>>T;
cin>>N>>M;
int xi,yi,xe,ye;
while(T--)
{
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
cin>>mg[i][j];
}
}
}
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
if(mg[i][j]=='S')
{
xi=i;
yi=j;
}
}
}
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
if(mg[i][j]=='E')
{
xe=i;
ye=j;
}
}
}
vector<Box>path;
mgpath(xi,yi,xe,ye,path);
return 0;
}
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int MAX = 100;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
char mg[MAX][MAX] = {};
int M, N;
int bfs(int sx, int sy, int ex, int ey)
{
queue<pair<int, int>> q;
vector<vector<int>> dist(M, vector<int>(N, -1));
q.push({sx, sy});
dist[sx][sy] = 0;
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
if (x == ex && y == ey)
return dist[x][y];
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < M && ny >= 0 && ny < N && mg[nx][ny] == '-' && dist[nx][ny] == -1)
{
q.push({nx, ny});
dist[nx][ny] = dist[x][y] + 1;
}
}
}
return -1; // 若无法到达终点，则返回-1
}
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> N >> M;
int sx, sy, ex, ey;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> mg[i][j];
if (mg[i][j] == 'S')
{
sx = i;
sy = j;
}
else if (mg[i][j] == 'E')
{
ex = i;
ey = j;
}
}
}
int shortestDistance = bfs(sx, sy, ex, ey);
cout << shortestDistance << endl;
}
return 0;
}
修改后的代码使用了广度优先搜索算法（BFS）来寻找从起点到终点的最短路径。在bfs函数中，我们使用一个队列和一个二维数组来记录每个位置的距离。通过遍历四个方向上的相邻位置，并将其入队，逐层扩展，直到找到终点或无法到达终点为止。
请注意，修改后的代码中没有使用vector来记录路径，而是使用了一个二维数组dist来记录每个位置的距离。最终的最短路径长度存储在dist[ex][ey]中。
参考我的博客文章