BFS implementation takes too much time for CSES labyrinth problem

Question

I am trying to solve the CSES Labyrinth problem:

You are given a map of a labyrinth, and your task is to find a path from start to end. You can walk left, right, up and down.

Input

The first input line has two integers n and m: the height and width of the map.

Then there are n lines of m characters describing the labyrinth. Each character is . (floor), # (wall), A (start), or B (end). There is exactly one A and one B in the input.

Output

First print "YES", if there is a path, and "NO" otherwise.

If there is a path, print the length of the shortest such path and its description as a string consisting of characters L (left), R (right), U (up), and D (down). You can print any valid solution.

Constraints

1 ≤ 𝑛,𝑚 ≤ 1000

Example

Input:

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

Output:

YES
9
LDDRRRRRU

I implemented a BFS algorithm. It solves all the test cases except one. In one of the test cases I get a time limit exceeded (TLE) error.

I have tried various approaches and watched many solutions on youtube as well, but there isn't anything standing out in those solutions that can resolve my problem or I might be missing something. Can someone spot where I am going wrong?

My code:

#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 is not efficient, it has a O(𝑛) time complexity where 𝑛 is the size of final_path. As you need to call this repeatedly, it amounts to a time complexity of O(𝑛²) where 𝑛 is the length of the found path.

For better efficiency, start your search from B and find A, so in the opposite direction. Then you can use final_path.push_back which has better efficiency -- amortised O(1) in your case, which means the complete path is built in O(𝑛) time complexity.

When you implement this change, make sure to store the letters in the path as if you were traversing it from A to B.