题目描述

小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。

小明只能向上下左右四个方向移动。

输入格式

输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。

每组输入的第一行是两个整数N和M（1<=N,M<=100）。

接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。

字符的含义如下：

‘S’：起点

‘E’：终点

‘-’：空地，可以通过

‘#’：障碍，无法通过

输入数据保证有且仅有一个起点和终点。

输出

对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。

样例输入

1

5 5

S-###

-----

##---

E#---

---##

样例输出

9

#include<stdio.h>
#include<string.h>
struct node
{
int x,y,step;
}s[10010];
char map[105][105];
int sx,sy,ex,ey;
int dir[4][2]={
	0,-1,0,1,1,0,-1,0
};
int visit[105][105];
int n,m;
int bfs()
{
	s[0].x=sx;
	s[0].y=sy;
	s[0].step=0;
	node cur,change;
	int rear=1,front =0;
	while(rear>front)
	{	
	     cur=s[front++];
		if(cur.x==ex&&cur.y==ey)
		return cur.step;
          for(int i=0;i<4;i++)
		   {
			int tx,ty;
			tx = cur.x+dir[i][0];
			ty = cur.y+dir[i][1];
			if(tx>=0&&ty<m&&tx<n&&ty>=0&&visit[tx][ty]==0&&(map[tx][ty]=='E'||map[tx][ty]=='-'))
			{
				
				visit[tx][ty]=1;
				change.x=tx;
				change.y=ty;
				change.step=cur.step + 1;
				s[rear++]=change;
			}
		  }	
	}
	return -1;
}
int main()
{
	int N;
	scanf("%d",&N);
	
	 while(N--)
	{
		memset(visit,0,sizeof(visit));
		char a[100][100];
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++)
		scanf("%s",map[i]);
		for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
		 if(map[i][j]=='S')
		 {
			sx=i;
			sy=j;
		 }
		 if(map[i][j]=='E')
		 {
			ex=i;
			ey=j;
		 }
		}
		printf("%d\n",bfs());
	}
}