迷宫
小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。
输入
输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：
‘S’：起点
‘E’：终点
‘-’：空地，可以通过
‘#’：障碍，无法通过
输入数据保证有且仅有一个起点和终点。
输出
对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。
样例输入
1
5 5
S-###
-----
##---
E#---
---##
样例输出
9
#include<iostream>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=1e3+10;
int n,m;
int dxy[4][2]={1,0,0,1,-1,0,0,-1};
char mp[maxn][maxn];
int vis[maxn][maxn];
struct node{
int x;
int y;
int level;
node(int xx,int yy,int llee)
{
x=xx;
y=yy;
level=llee;
}
};
queue<node>q;
int check(int x,int y){
if(x<0 || x>=n || y<0 || y>=m ||vis[x][y] ||mp[x][y]=='#')
return 0;
return 1;
}
int bfs(int x,int y)
{
vis[x][y]=1;
q.push(node(x,y,0)); //先进队列，
while(!q.empty()){ //队列不为空
int X,Y,Z;
node a=q.front();
X=a.x; //出一个
Y=a.y;
Z=a.level;
if(mp[a.x][a.y]=='E') //终止条件
return Z;
q.pop();
for(int i=0;i<4;i++){ //循环4个方向
int dx=a.x+dxy[i][0];
int dy=a.y+dxy[i][1];
if(check(dx,dy)){
vis[dx][dy]=1;
q.push(node(dx,dy,a.level+1)); //满足条件加入节点
}
}
}
}
int main()
{
int k;
cin>>k;
while(k--){
cin>>n>>m;
int nn,mm;
memset(mp,0,sizeof(mp));
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>mp[i][j];
if(mp[i][j]=='S')
{
nn=i;
mm=j;
}
}
}
cout<<bfs(nn,mm);
}
}