本文共 2005 字，大约阅读时间需要 6 分钟。

阿尔吉侬是一只聪明的小白鼠，它擅长在迷宫中寻找最短路径。研究员们在迷宫中设置了一个终点，放置了一块阿尔吉侬最喜欢的奶酪。为了确定阿尔吉侬吃到奶酪所需的最少时间，我们需要使用广度优先搜索（BFS）算法来计算最短路径。

首先，我们需要读取输入数据。输入包括多个测试用例，每个测试用例包含一个R行C列的地图。地图中，'S'表示起点，'E'表示终点，'#'表示墙壁，'.'表示可以通行的格子。我们的任务是找到从'S'到'E'的最短路径。

对于每个测试用例，我们首先读取地图并标记起点和终点的位置。然后，我们使用BFS算法来探索迷宫。BFS算法通过逐层扩展，确保找到最短路径。每次从队列中取出当前位置，检查是否到达终点。如果没有到达终点，则检查四个方向（上、下、左、右）的相邻格子。对于每个相邻格子，如果它是通行的且未被访问过，我们标记它并将其添加到队列中。

如果在BFS过程中到达了终点，我们记录当前步数作为最短路径。如果无法到达终点，则输出“oop!”。

以下是实现代码：

#include 
   
    using namespace std;int n, m, sx, sy, ex, ey;int dx[] = {0, 1, 0, -1};int dy[] = {1, 0, -1, 0};struct node {    int x;    int y;    int step;};bool vis[N][N];int bfs() {    queue
    
      q;    node p;    p.x = sx;    p.y = sy;    p.step = 0;    vis[p.x][p.y] = true;    q.push(p);        while (!q.empty()) {        node xx = q.front();        q.pop();        if (xx.x == ex && xx.y == ey) {            return xx.step;        }        for (int i = 0; i < 4; ++i) {            int x1 = xx.x + dx[i];            int y1 = xx.y + dy[i];            if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m) {                if (!vis[x1][y1] && a[x1][y1] != '#') {                    vis[x1][y1] = true;                    node p = {x1, y1, xx.step + 1};                    q.push(p);                }            }        }    }    return -1;}int main() {    int t;    cin >> t;    for (; t--; ) {        memset(vis, false, sizeof(vis));        cin >> n >> m;        for (int i = 0; i < n; ++i) {            string s;            cin >> s;            for (int j = 0; j < m; ++j) {                if (s[j] == 'S') {                    sx = i;                    sy = j;                } else if (s[j] == 'E') {                    ex = i;                    ey = j;                }                a[i][j] = s[j];            }        }        int h = bfs();        if (h != -1) {            cout << h << endl;        } else {            cout << "oop!" << endl;        }    }}
    
   

这个代码首先读取输入数据，找到起点和终点的位置。然后使用BFS算法探索迷宫，计算最短路径。如果无法到达终点，输出“oop!”。该代码确保了在最坏情况下也能高效运行，适用于给定的数据范围。

转载地址：http://dumb.baihongyu.com/