算法1

思路:广搜(补充:广搜可以求出最短路径,深搜只能求出一种路径,而且广搜不容易出错,深搜是栈,光搜是队列)

函数

void memset(void s, int ch, size_t n);

函数解释：将s中当前位置后面的n个字节 （typedef unsigned int size_t ）用 ch 替换并返回 s 。

make_pair函数无需写出型别， 就可以生成一个pair对象

pair的应用

pair是将2个数据组合成一个数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一个结构体，主要的两个成员变量是first second 因为是使用struct不是class，所以可以直接使用pair的成员变量

C++ 代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;

#define x first
#define y second

typedef long long LL;

typedef pair<int,int>PII;
const int N=210;

int n,m;
char g[N][N];
int dist[N][N];

int bfs(PII start,PII end){
    queue<PII> q;
    memset(dist,-1,sizeof dist);//数组初始化

    dist[start.x][start.y]=0;//起始点赋值0

    q.push(start);

    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//定义四个方向

    while(q.size()){//循环条件:队列不空
        auto t=q.front();
        q.pop();//这里为什么要弹出呢?有点糊涂

        if(t==end) return dist[t.x][t.y];//如果直接为终点返回

        for(int i=0;i<4;i++){

            int x=t.x+dx[i],y=t.y+dy[i];

            if(x<0||x>=n|| y<0 || y>=m) continue;//越界
            if(g[x][y]=='#')continue;//碰墙
            if(dist[x][y]!=-1 )continue;//便利过

            dist[x][y]=dist[t.x][t.y]+1;//未遍历过,步数加1

            if(end==make_pair(x,y)) return dist[x][y];//make_pair来生成我们需要的pair
            q.push({x,y});//将下一个坐标放到队列总去

        }
    }

   return -1; 
}

int main(){

    int t;
    scanf("%d",&t);

    while(t--){
        scanf("%d%d",&n,&m);
            for(int i=0;i<n;i++)
                scanf("%s",g[i]);

        PII start,end;
        for(int i=0;i<n;i++)//处理起点\终点
         for(int j=0;j<m;j++)
            if(g[i][j]=='S')start={i,j};
            else if(g[i][j]=='E')end={i,j};

    int distance=bfs(start,end);
    if(distance == -1)puts("oop!");
    else printf("%d\n",distance);

    }

    return 0;
}