#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;
}
Auto comment: topic has been updated by Forrest_Gump (previous revision, new revision, compare).
Try step by step.
You don't have to optimize, your implementation is incorrect.
Your BFS implementation is incorrect.
You should mark as a visited when it is in the queue, but you mark it when you got it extracted from the queue. This is the reason of TLE, you infinitely add to the queue values, that are already in the queue.
I have marked it visited twice. Even When it is pushed in the queue!
This can Help : CF BLOG Instead of storing string in Queue, try generating it when you arrive at the end, for generation of answer string , you can store (parent child )pair in map(STL). For Hint You can check : My Code
Thanks a lot!!! I didn't know about the complexity of adding char to string!
I have been watching your videos and streams lately they are pretty cool, keep the good work going :)