sdjzu1102迷宫问题

题目描述

小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。

输入格式

输入包含多组测试数据。输入的第一行是一个整数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());}
}