迷宫问题-题解(C语言代码)

开始用dfs写，果然用递归写会超时，剪枝又麻烦，所以选择用bfs

直接贴代码，代码都有注释

#include<stdio.h>
#include<string.h> 
#include<stdlib.h>
char a[100][100];//用于存储迷宫 
int m,n;
int b[100][100];//标记是否访问 
int queue[10000][3];//存储点及其走过的路程长短 
int x[]={0,0,1,-1};
int y[]={1,-1,0,0};
int bfs(int i,int j)//广度优先遍历 
{
int k,tx,ty,cx,cy;
int head=0,tail=0;
int count;
queue[tail][0]=i;
queue[tail][1]=j;
queue[tail][2]=0;//初始路程为0 
tail++;
b[i][j]=0;
while(head<tail)//当队列中不为空时循环 
{
    cx=queue[head][0];
    cy=queue[head][1];
    count=queue[head][2];//取出队头元素及其路程 
    head++;
    for(k=0;k<4;k++)
    {
        tx=cx+x[k];
        ty=cy+y[k];
        if(tx>=0&&tx<m&&ty>=0&&ty<n&&b[tx][ty]&&a[tx][ty]!='#')//四个方向 
        {
        if(a[tx][ty]=='E')//如果到达出口则返回，广度优先遍历先找到的第一个是最短路程 
        {
            return count+1;
        }
        queue[tail][0]=tx;
        queue[tail][1]=ty;
        queue[tail][2]=count+1;//上一点的路程加1后放入队列 
        tail++;
        b[tx][ty]=0;//标记置0 
        }
    }
}
return -1;
} 
int main()
{
int T,i,j,k,z;//数据的组数
char c;
scanf("%d",&T);
for(i=0;i<T;i++)
{
    scanf("%d%d",&m,&n);//m：行，n：列
    getchar();//读取换行 
    for(j=0;j<m;j++) 
    {
        for(k=0;k<n;k++)
        {
            c=getchar();
            a[j][k]=c;
        }
    getchar();//读取换行 
    }
    for(j=0;j<m;j++) 
    {    
        for(k=0;k<n;k++)
        {    
            b[j][k]=1;
        }
    }
    for(j=0;j<m;j++) 
    {    
        for(k=0;k<n;k++)
        {    
            if(a[j][k]=='S') 
            printf("%d\n",bfs(j,k));
        }
    }
} 
}