走 迷 宫

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

题目大意：给定一个$N\times M$字符矩阵描述的迷宫（‘#’表示墙壁，‘.’表示可以通行），保证有且仅有一个起点$S$和终点$E$。求从起点到终点的最短距离，若无法到达则输出“oop!”。

小技巧：

• 地图的读取方式

char g[N][N];
for (int i = 0; i < n; i ++) cin >> g[i]; //每次读入一个字符串（一维数组）

• 枚举方向

int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};
for (int i = 0; i < 4; i ++)
{
    
	int x = t.x + dx[i], y = t.y + dy[i]; //(x, y)为当前所处理的邻接点的坐标，(t.x, t.y)为原点的坐标
	...
}

• dist数组用于记录每个可达的点到起点的距离，初始化为-1，从而同时也起到st数组的判重作用。

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

#define x first
#define y second
typedef pair<int, int> PII;
int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, 1, 0, -1};

const int N = 210;
char g[N][N];
int dist[N][N];

int n, m; //迷宫规模

int bfs(PII start, PII end) //传入起点和终点的坐标
{
    
    memset(dist, -1, sizeof(dist));
    queue<PII> q;
    
    q.push(start);
    dist[start.x][start.y] = 0;

    while (!q.empty())
    {
    
        PII t = q.front(); q.pop();

        for (int i = 0; i < 4; i ++) //枚举4个方向
        {
    
            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;

            if (end == make_pair(x, y)) return dist[x][y];
            else q.push({
    x, y});
        }
    }

    return -1; //迷宫中所有可达的点都被遍历了一次还没有走到终点，说明终点不可达
}

int main()
{
    
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> 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 cout << distance;
    
    return 0;
}