【题解】献给阿尔吉侬的花束

题目链接：献给阿尔吉侬的花束

BFS

1. 宽度优先遍历，适合有四个方向的棋盘类最短路问题，关键在于所有点之间的距离必须相同。
2. 一般所需要的数据结构有：队列，标记数组，距离数据。通常标记数组可省略，看个人习惯。

BFS C++ 117ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second


const int N = 200 + 10;

string g[N];
int r, c;
int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
bool st[N][N];
int d[N][N];

int bfs(int sx, int sy)
{
    int u = 1;
    queue<PII> q;
    q.push({sx, sy});
    d[sx][sy] = 0;
    
    while (q.size())
    {
        int x = q.front().x, y = q.front().y;
        q.pop();

        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < r && b >= 0 && b < c && g[a][b] != '#' && !st[a][b])
            {
                st[a][b] = true;
                if (g[a][b] == 'E')
                {
                    return d[x][y] + 1;
                }
                q.push({a, b});
                d[a][b] = d[x][y] + 1;
            }
        }
    }
    return -1;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> r >> c;

        memset(st, false, sizeof st);
        bool flag = false;
        int x, y;
        for (int i = 0; i < r; i ++ )
        {
            cin >> g[i];
            if (flag == false)
            {
                for (int j = 0; j < g[i].size(); j ++ )
                {
                    if (g[i][j] == 'S') 
                    {
                        x = i, y = j;
                        flag = true;
                    }
                }
            }
        }

        int ans = bfs(x, y);
        ans == -1 ? cout << "oop!" << endl : cout << ans << endl;
    }

    return 0;
}