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!