对于 CSES 迷宫问题，BFS 实施需要太多时间

Question

我正在尝试解决 CSES 迷宫问题:

您将获得一张迷宫地图，您的任务是找到从起点到终点的路径。您可以左、右、上、下行走。

输入

第一输入行有两个整数n和m：地图的高度和宽度。

那么有n行m个字符描述迷宫。每个字符都是

.

（地板）、

#

（墙壁）、

A

（开始）或

B

（结束）。输入中恰好有 1 个

A

和 1 个

B

。

输出

如果有路径，首先打印“YES”，否则打印“NO”。

如果存在路径，则打印最短路径的长度及其描述，作为由字符

L

（左）、

R

（右）、

U

（上）和

D

（向下）。您可以打印任何有效的解决方案。

限制

1 ≤ 𝑛,𝑚 ≤ 1000

示例

输入：

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

输出：

YES
9
LDDRRRRRU

我实现了BFS算法。它解决了除一个之外的所有测试用例。在其中一个测试用例中，我收到“超出时间限制”(TLE) 错误。 我尝试了各种方法，也在 youtube 上观看了许多解决方案，但这些解决方案中没有任何突出的内容可以解决我的问题，或者我可能会错过一些东西。有人能发现我哪里出错了吗？

我的代码：

#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;
}

Answer 1

final_path.insert

效率不高，它的时间复杂度为 O(𝑛)，其中𝑛是

final_path

的大小。由于您需要重复调用此函数，因此时间复杂度为 O(𝑛²)，其中 𝑛 是找到的路径的长度。为了提高效率，从 B 开始搜索并找到 A，所以方向相反。然后你可以使用

final_path.push_back

，它具有更好的效率 - 在你的情况下摊销 O(1) ，这意味着完整的路径是在 O(𝑛) 时间复杂度中构建的。

实施此更改时，请确保将字母存储在路径中，就像从 A 遍历到 B 一样。