问题 C:迷宫问题
题目描述
小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。
输入
输入包含多组测试数据。输入的第一行是一个整数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 note
{int x;int y;int f;int s;
};
int main()
{struct note que[15000];int a[110][110]={0},book[110][110]={0};int next[4][2]={
{0,1},{1,0},{0,-1},{-1,0}};int head,tail;int i,j,k,n,m,startx,starty,p,q,tx,ty,flag,t;char s[110][110],s1;while(scanf("%d",&t)!=EOF){while(t--){memset(a,0,sizeof(a));memset(book,0,sizeof(book));scanf("%d%d",&n,&m);getchar();for(i=0;i<n;i++){ scanf("%s",&s[i]);}for(i=0;i<n;i++){for(j=0;j<m;j++){if(s[i][j]=='-')a[i+1][j+1]=0;else if(s[i][j]=='#')a[i+1][j+1]=1;else if(s[i][j]=='S'){startx=i+1;starty=j+1;a[i+1][j+1]=0;}else if(s[i][j]=='E'){p=i+1;q=j+1;a[i+1][j+1]=0;}}} head=tail=1;que[tail].x=startx;que[tail].y=starty;que[tail].f=0;que[tail].s=0;tail++;book[startx][starty]=1;flag=0;while(head<tail){for(k=0;k<=3;k++){tx=que[head].x+next[k][0];ty=que[head].y+next[k][1];if(tx<1||tx>n||ty<1||ty>m)continue;if(a[tx][ty]==0&&book[tx][ty]==0){book[tx][ty]=1;que[tail].x=tx;que[tail].y=ty;que[tail].f=head;que[tail].s=que[head].s+1;//printf("que===%d \n",que[tail].s);tail++;}if(tx==p&&ty==q){flag=1;break;}}if(flag==1){break;} head++;}if(que[tail-1].s==0)printf("-1\n");elseprintf("%d\n",que[tail-1].s);} } return 0;
}