BFS广度优先搜索

解题思路:

注意事项:如果不是多组数据，代码会简洁一些，注释有些没有根据本题改，代码是套用自己之前写过题的模板

参考代码:

#include<iostream>
#include<queue>  //使用队列需要的头文件（也可以用数组手动模拟队列）
#include<cstring>//使用memset()需要用到的头文件
using namespace std;

typedef pair<int ,int> PII;//定义坐标的数据结构

const int N=110;



//char g[N][N];//存储地图
//int d[N][N];//记录每个点到起点的距离

int bfs(int a,int b,int e,int f,int n,int m,char g[][N],int d[][N])

{
    queue <PII> q;//定义一个坐标队列
    q.push({e,f});//起点进队
    
  
    
    d[e][f]=0;//表示起点走过了
    
    int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};//向四个方向扩展的坐标数组(偏移量技巧)
    while(!q.empty()) //队列不空
    {
        auto t=q.front();//取队头元素
        q.pop();         //队头元素出队
        for(int i=0;i<4;i++)  //分别向四个方向走
        {
            int x=t.first+dx[i],y=t.second+dy[i];//（x,y）为走后的坐标
            //首先(x,y)不能越界, 然后g[x][y] == 0说明可以走(g[x][y] == 1说明是障碍物)
            //最后是只更新未被访问的点到源点的距离 (要求d[x][y] == -1)
            if(x>=0&&x<n&&y>=0&&y<m&&(g[x][y]=='-'||g[x][y]=='E')&&d[x][y]==-1)
            {
                d[x][y]=d[t.first][t.second]+1;//更新未被访问的点到起点的距离（其实就是扩展前的点到起点的距离+1就行了）
                q.push({x,y}); //新坐标入队                          
            }
            
        }
    }
    return d[a][b];//输出右下角点据起点的距离即可
}
int main()
{    int t;
    scanf("%d",&t);
    while(t--)
    {   char g[N][N];
        int d[N][N];
        int a,b,e,f,n,m;

    scanf("%d%d",&n,&m);
   for(int i=0;i<n;i++)
   {
       for(int j=0;j<m;j++)
       {
           cin>>g[i][j];
           if(g[i][j]=='S') e=i,f=j;
           if(g[i][j]=='E') a=i,b=j;
           d[i][j]=-1;
       }
   }
    
    
    printf("%d\n",bfs(a,b,e,f,n,m,g,d));
    }
    return 0;
}