CSES Labyrinth TLE

The problem link: CSES - Labyrinth
My solution: https://cses.fi/problemset/result/2229112/

Code:

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll int
#define pll pair< long long int, long long int >
#define f first
#define s second 
#define mod 1000000007
#define rep( i, a, b ) for( long long int i = a; i < b; i++ )
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
 
const ll N = 1005;
ll n, m;
char a[ N ][ N ];
bool vis[ N ][ N ];
ll par[ N ][ N ];
 
ll dx[ 4 ] = { 1, -1, 0, 0 };
ll dy[ 4 ] = { 0, 0, 1, -1 };
string direction = "DURL";
 
void solve()
{
    cin >> n >> m;
    pll beg, en;
    memset( vis, false, sizeof( vis ));
 
    rep( i, 0, n )
    rep( j, 0, m )
    {    
        cin >> a[ i ][ j ];
        if( a[ i ][ j ] == 'A' )
            beg = { i, j };
        else if( a[ i ][ j ] == 'B' )
            en = { i, j };
    }
 
    queue< pll > q;
    q.push( beg );
    vis[ beg.f ][ beg.s ] = true;    
 
    while( !q.empty())
    {
        pll c = q.front();
        q.pop();
        if( a[ c.f ][ c.s ] == 'B' )
            break;
            
        rep( i, 0, 4 )
        {
            ll x = c.f + dx[ i ];
            ll y = c.s + dy[ i ];
 
            if(!( x < 0 || x >= n || y < 0 || y >= m || vis[ x ][ y ] || a[ x ][ y ] == '#' ))
            {
                vis[ x ][ y ] = true;
                q.push({ x, y });
                par[ x ][ y ] = i;
            }
        }
    }
 
    if( vis[ en.f ][ en.s ])
    {
        cout << "YES\n";
        string ans = "";
 
        while( en != beg )
        {
            ll i = par[ en.f ][ en.s ];
            ans = direction[ i ] + ans;
            en.f = en.f - dx[ i ];
            en.s = en.s - dy[ i ];
        }
        cout << ans.size() << "\n" << ans << "\n";
    }
    else
    {
        cout << "NO\n";
    }
}
 
int main()
{
    FIO;
    solve();
 
    return 0;
}


I'm getting tle in one test case. Can anyone please guide me how can resolve this? Thanks in advance!

The testcase 18 might giving you tle .
Do one thing don’t complete the whole bfs .
Just print the ans as soon as you reach to the destination and return .

ans = direction[ i ] + ans;

This step will take O(n) time.
You must write ans += direction[i] and reverse the string when you exit the loop.

string = char + string or string = string + char or string = string + string all of these will take O(n) time.
Only step that is executed in constant time is string += char (it’s equivalent to push_back).

4 Likes

That helped a lot. Thanks vishaaaal!

1 Like

Thanks Vishaaa <3