I am trying to solve 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;
}