【acwing 寒假每日一题（入门组）】day25献给阿尔吉侬的花束

题目来源：

题目描述

阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。

今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。

现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。

迷宫用一个 R×C 的字符矩阵来表示。

字符 S 表示阿尔吉侬所在的位置，字符 E 表示奶酪所在的位置，字符 # 表示墙壁，字符 . 表示可以通行。

阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。

输入格式
第一行是一个正整数 T，表示一共有 T 组数据。

每一组数据的第一行包含了两个用空格分开的正整数 R 和 C，表示地图是一个 R×C 的矩阵。

接下来的 R 行描述了地图的具体内容，每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。

输出格式
对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。

若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。

每组数据的输出结果占一行。

数据范围
1<T≤10,
2≤R,C≤200
输入样例：

3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.

输出样例：

5
1
oop!

思路

默一遍bfs代码就好了
这个和使用bfs实现的的Flood Fill算法很像，但是不一样，因为Flood Fill算法还可以使用dfs实现，但是这里要求最短路只能用bfs
参考 【acwing 寒假每日一题（入门组）】day4红与黑

代码

bfs

#include<bits/stdc++.h>

using namespace std;

const int N=210;

typedef pair<int,int> PII;

int n,m;
char g[N][N];
int d[N][N];
int dx[] = {0,1,0,-1}, dy[] = {1, 0, -1, 0};

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>g[i];
        
        queue<PII> q;
        int a,b;
        memset(d,-1,sizeof d);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(g[i][j]=='S')
                {
                    d[i][j]=0;
                    q.push({i,j});
                }else if(g[i][j]=='E')
                {
                    a=i,b=j;
                }
            }
        while(q.size())
        {
            auto t=q.front();
            q.pop();
            for(int i=0;i<4;i++)
            {
                int x=t.first+dx[i],y=t.second+dy[i];
                if(x>=0 && x<n && y>=0 && y<m && g[x][y]!='#' && d[x][y]==-1)
                {
                    d[x][y]=d[t.first][t.second]+1;
                    if(g[x][y]=='E')
                    {
                        q=queue<PII>(); //因为找到答案了 没有使用函数 无法直接返回 就只能曲线救国了
                        break;
                    }
                    q.push({x,y});
                }
            }
        }
        if(d[a][b]!=-1) cout<<d[a][b]<<endl;
        else cout<<"oop!"<<endl;
    }
}