题解

思路

宽搜

代码

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

#define Fir first
#define Sec second
typedef pair<int ,int > PII;
const int N = 210;
const int INF = 1e6;

char map[N][N];//用于存储地图数据
int dist[N][N];//用于存储距离

//宽搜得到
int bfs(int sr , int sc , int er , int ec)
{
    bool flag = false;//标记找没找到
    memset(dist , 0 , sizeof dist);//先标记为0


    queue<PII> que;//队列存储数据
    que.push({sr , sc});//从sr, sc开始
    dist[sr][sc] = 0;

    //开始寻找
    while(que.size())
    {
        PII node = que.front();//取出第一个数据，进行遍历
        que.pop();//拿出去第一个数据

        int dx[] = {0,1,0,-1} , dy[] = {1,0,-1,0};

        //用取出数据进行宽搜
        //四个方向走
        for(int i = 0 ; i<4 ; i++)
        {
            int tx = node.Fir + dx[i] , ty = node.Sec + dy[i];

            //看看是否可以行走
            if((map[tx][ty] == '.' || map[tx][ty] == 'E') && dist[tx][ty] == 0)
            {
                //可以行走
                //判断是否为终点
                if(tx == er && ty == ec)//遇到终点直接返回 
                {
                    flag = true;
                    return dist[node.Fir][node.Sec] + 1;
                }

                //不是终点，继续遍历
                que.push({tx,ty});
                dist[tx][ty] = dist[node.Fir][node.Sec] + 1;

            }

        }

    }

    if(!flag) return INF;

}

int main()
{
    int T;//T组数据 , r:行, c:列
    cin>>T;

    while(T--)
    {
        memset(map , '#' ,sizeof map);//重置数据
        //输入行、列数据
        int r , c;
        cin>>r>>c;

        //标记位置
        int sr , sc;
        int er , ec;

        //输入地图数据
        for(int i = 0 ; i<r ; i++)
        {
            for(int j = 0 ; j<c ; j++)
            {
                cin>>map[i][j];
                if(map[i][j] == 'S') sr = i , sc = j;
                if(map[i][j] == 'E') er = i , ec = j;
            }
        }

        int ans = bfs(sr , sc , er , ec);//宽搜
        if(ans == INF) cout<<"oop!"<<endl;
        else cout<<ans<<endl;

    }

    return 0;
}