CSES迷宫问题BFS实现遇超时（TLE），求问题排查与优化

问题描述 #

给定一张迷宫地图，任务是找到从起点到终点的最短路径，可上下左右移动。

输入格式 #

• 第一行输入两个整数n和m：地图的高度和宽度。
• 接下来n行，每行m个字符描述迷宫。字符包括：
  • .：可行走区域
  • #：墙壁
  • A：起点（唯一）
  • B：终点（唯一）

输出格式 #

• 若存在路径，先输出"YES"，否则输出"NO"。
• 若存在路径，额外输出最短路径的长度，以及由L（左）、R（右）、U（上）、D（下）组成的路径字符串（任意有效解均可）。

约束条件 #

1 ≤ n,m ≤ 1000

示例输入 #

5 8
########
#.A#...#
#.##.#B#
#......#
########

示例输出 #

YES
9
LDDRRRRRU

问题情况 #

实现的BFS算法可通过所有测试用例，但其中一个测试用例出现time limit exceeded（TLE）错误。尝试过多种方法，也参考了不少解决方案，未找到关键问题，请求排查。

代码实现 #

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool vis[1001][1001];
char path[1001][1001];
queue<pair<int, int>> q;
vector<pair<int, int>> moves = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1}};
vector<char> final_path;
int n, m, sx, sy, ex, ey;

bool is_valid(int i, int j)
{
    if (i < 0 || i >= n || j < 0 || j >= m)
    {
        return false;
    }
    if (vis[i][j])
        return false;
    return true;
}

bool bfs(int i, int j)
{
    vis[i][j] = true;

    q.push({i, j});

    while (!q.empty())
    {
        pair<int, int> f = q.front();
        q.pop();
        if (f.first == ex && f.second == ey)
        {
            int p = f.first;
            int r = f.second;
            while (p != sx or r != sy)
            {
                // cout << p << r << sx << sy << endl;
                if (path[p][r] == 'D')
                {
                    final_path.insert(final_path.begin(), 'D');
                    p--;
                }
                if (path[p][r] == 'U')
                {
                    final_path.insert(final_path.begin(), 'U');
                    p++;
                }
                if (path[p][r] == 'R')
                {
                    final_path.insert(final_path.begin(), 'R');
                    r--;
                }
                if (path[p][r] == 'L')
                {
                    final_path.insert(final_path.begin(), 'L');
                    r++;
                }
            }
            // cout << p << r << sx << sy << endl;
            return true;
        }
        else
        {
            for (int k = 0; k < 4; k++)
            {
                if (is_valid(f.first + moves[k].first, f.second + moves[k].second))
                {
                    vis[f.first + moves[k].first][f.second + moves[k].second] = true;
                    q.push({f.first + moves[k].first, f.second + moves[k].second});
                    if (k == 0)
                        path[f.first + moves[k].first][f.second + moves[k].second] = 'D';
                    if (k == 1)
                        path[f.first + moves[k].first][f.second + moves[k].second] = 'U';
                    if (k == 2)
                        path[f.first + moves[k].first][f.second + moves[k].second] = 'R';
                    if (k == 3)
                        path[f.first + moves[k].first][f.second + moves[k].second] = 'L';
                }
            }
        }
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            char c;
            cin >> c;
            if (c == 'A')
            {
                sx = i, sy = j;
            }
            if (c == 'B')
            {
                ex = i, ey = j;
            }
            if (c == '#')
            {
                vis[i][j] = true;
            }
        }
    }

    if (bfs(sx, sy))
    {
        cout << "YES" << endl
             << final_path.size() << endl;
        for (auto i : final_path)
            cout << i;
    }
    else
    {
        cout << "NO";
    }

    return 0;
}

问题排查与解决方案 #

核心问题1：路径拼接的时间开销 #

回溯路径时使用final_path.insert(final_path.begin(), char)，每次插入到vector头部的时间复杂度为O(k)（k为当前路径长度）。对于最大可能1e6长度的路径（1000×1000地图），总时间复杂度会达到O(k²)，这是导致TLE的关键原因。

解决方法：
从终点回溯到起点时，将字符添加到vector尾部，最后反转整个vector。每次插入操作变为O(1)，反转操作仅为O(k)，总时间复杂度降至O(k)。

核心问题2：输入读取的隐藏开销 #

虽然添加了ios_base::sync_with_stdio(false);，但逐个字符读取cin >> c的方式，在处理大输入时会有额外开销。更高效的方式是整行读取字符串后再逐个访问字符。

解决方法：
替换内层循环为整行读取字符串：

for (int i = 0; i < n; i++)
{
    string s;
    cin >> s;
    for (int j = 0; j < m; j++)
    {
        char c = s[j];
        // 后续处理逻辑不变
    }
}

其他优化点（可选） #

• 将全局队列q改为BFS函数内的局部变量，避免潜在的残留数据问题（本题仅运行一次，影响较小）。
• 回溯路径时，将四个if改为else if，减少不必要的分支判断。

修改后的关键代码片段 #

回溯路径部分

if (f.first == ex && f.second == ey)
{
    int p = f.first;
    int r = f.second;
    while (p != sx || r != sy)
    {
        if (path[p][r] == 'D')
        {
            final_path.push_back('D');
            p--;
        }
        else if (path[p][r] == 'U')
        {
            final_path.push_back('U');
            p++;
        }
        else if (path[p][r] == 'R')
        {
            final_path.push_back('R');
            r--;
        }
        else if (path[p][r] == 'L')
        {
            final_path.push_back('L');
            r++;
        }
    }
    reverse(final_path.begin(), final_path.end());
    return true;
}

输入读取部分

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); // 进一步加速cin
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++)
        {
            char c = s[j];
            if (c == 'A')
            {
                sx = i, sy = j;
            }
            if (c == 'B')
            {
                ex = i, ey = j;
            }
            if (c == '#')
            {
                vis[i][j] = true;
            }
        }
    }
    // 后续逻辑不变
}

内容的提问来源于stack exchange，提问作者Yash Rai