I have commented the code at places. I can't understand why the code gives TLE. 1 test case gives TLE.I have tried to optimise it as much as I could but still TLE. Help would be appreciated. I have used breadth first search to solve the problem.[The problem](https://cses.fi/problemset/task/1193/)↵
↵
Also what would be worst case complexity?↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
long long n,m;↵
↵
string pr="";↵
↵
char ch[1002][1002];↵
↵
long long dx[4]={1,0,-1,0};↵
long long dy[4]={0,1,0,-1};↵
↵
/*checks valididty of cell*/↵
↵
bool is(long long x,long long y)↵
{↵
//cout<<ch[x][y]<<" ";↵
return (x>=0&&y>=0&&x<n&&y<m&&ch[x][y]!='#');↵
}↵
↵
string l[4]={"D","R","U","L"};↵
↵
struct vert↵
{↵
long long a;↵
long long b;↵
string c;↵
};↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
long long x,y,i,j,sti,stj,ndi,ndj;↵
cin>>n>>m;↵
long long vis[n+1][m+1];↵
for(i=0;i<n;i++)↵
{↵
for(j=0;j<m;j++)↵
{↵
vis[i][j]=0;↵
cin>>ch[i][j];↵
/*start*/↵
if(ch[i][j]=='A'){sti=i;stj=j;}↵
/*end*/↵
if(ch[i][j]=='B'){ndi=i;ndj=j;}↵
}↵
}↵
queue<vert> q;↵
/*The queue wil store the coordinate as well as string*/↵
q.push({sti,stj,""});↵
/*bfs*/↵
while(!q.empty())↵
{↵
x=q.front().a;↵
y=q.front().b;↵
string s=q.front().c;↵
vis[x][y]=1;↵
q.pop();↵
for(i=0;i<4;i++)↵
{↵
if(is(x+dx[i],y+dy[i])&&!vis[x+dx[i]][y+dy[i]])↵
{↵
/*pr is required string that we wnt to print*/↵
if(x+dx[i]==ndi&&y+dy[i]==ndj&&(s.length()+1<pr.length()||pr.length()==0)){pr=s+l[i];}↵
if(pr.size()==0||s.length()+1<pr.length()){q.push({x+dx[i],y+dy[i],s+l[i]});}↵
vis[x+dx[i]][y+dy[i]]=1;↵
}↵
}↵
}↵
if(pr==""){cout<<"NO";exit(0);}↵
else↵
{↵
cout<<"YES"<<"\n";↵
cout<<pr.length()<<"\n";↵
cout<<pr<<"\n";↵
}↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
↵
Also what would be worst case complexity?↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
long long n,m;↵
↵
string pr="";↵
↵
char ch[1002][1002];↵
↵
long long dx[4]={1,0,-1,0};↵
long long dy[4]={0,1,0,-1};↵
↵
/*checks valididty of cell*/↵
↵
bool is(long long x,long long y)↵
{↵
//cout<<ch[x][y]<<" ";↵
return (x>=0&&y>=0&&x<n&&y<m&&ch[x][y]!='#');↵
}↵
↵
string l[4]={"D","R","U","L"};↵
↵
struct vert↵
{↵
long long a;↵
long long b;↵
string c;↵
};↵
↵
int main()↵
{↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
long long x,y,i,j,sti,stj,ndi,ndj;↵
cin>>n>>m;↵
long long vis[n+1][m+1];↵
for(i=0;i<n;i++)↵
{↵
for(j=0;j<m;j++)↵
{↵
vis[i][j]=0;↵
cin>>ch[i][j];↵
/*start*/↵
if(ch[i][j]=='A'){sti=i;stj=j;}↵
/*end*/↵
if(ch[i][j]=='B'){ndi=i;ndj=j;}↵
}↵
}↵
queue<vert> q;↵
/*The queue wil store the coordinate as well as string*/↵
q.push({sti,stj,""});↵
/*bfs*/↵
while(!q.empty())↵
{↵
x=q.front().a;↵
y=q.front().b;↵
string s=q.front().c;↵
vis[x][y]=1;↵
q.pop();↵
for(i=0;i<4;i++)↵
{↵
if(is(x+dx[i],y+dy[i])&&!vis[x+dx[i]][y+dy[i]])↵
{↵
/*pr is required string that we wnt to print*/↵
if(x+dx[i]==ndi&&y+dy[i]==ndj&&(s.length()+1<pr.length()||pr.length()==0)){pr=s+l[i];}↵
if(pr.size()==0||s.length()+1<pr.length()){q.push({x+dx[i],y+dy[i],s+l[i]});}↵
vis[x+dx[i]][y+dy[i]]=1;↵
}↵
}↵
}↵
if(pr==""){cout<<"NO";exit(0);}↵
else↵
{↵
cout<<"YES"<<"\n";↵
cout<<pr.length()<<"\n";↵
cout<<pr<<"\n";↵
}↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
