在 CSES 问题迷宫的一个测试用例中获得 TLE

Question

该问题是一个基于网格的图问题，需要使用 BFS 来解决。我已经在 中编写了代码，并解决了除一个之外的所有测试用例。在其中一个测试用例中，我得到了 TLE。我尝试了各种方法，也在 youtube 上观看了许多解决方案，但这些解决方案中没有任何突出的内容可以解决我的问题，或者我可能会错过一些东西。有人可以指导我哪里出错了。

问题：https://cses.fi/problemset/task/1193/

下面是我实施的解决方案，它能够通过所有 TC，除了给出 TLE 的一个之外

该问题是一个基于网格的图问题，需要使用 BFS 来解决。我已经在 中编写了代码，并解决了除一个之外的所有测试用例。在其中一个测试用例中，我得到了 TLE。我尝试了各种方法，也在 youtube 上观看了许多解决方案，但这些解决方案中没有任何突出的内容可以解决我的问题，或者我可能会错过一些东西。有人可以指导我哪里出错了。

问题：https://cses.fi/problemset/task/1193/

下面是我实施的解决方案，它能够通过所有 TC，除了给出 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;
    }

Answer 1

final_path.insert

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

final_path

的大小。由于您需要重复调用此函数，因此时间复杂度为 O(𝑛²)，其中 𝑛 是找到的路径的长度。

为了提高效率，从 B 开始搜索并找到 A，所以方向相反。然后你可以使用

final_path.push_back

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

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