Forrest_Gump's blog

By Forrest_Gump, history, 3 months ago, In English

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

Also what would be worst case complexity?

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;
}

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it