CSES Labryinth TLE?
Разница между en1 и en2, 23 символ(ов) изменены
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>↵


История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Forrest_Gump 2020-11-26 17:22:04 23 Tiny change: 'ives TLE. I have tri' -> 'ives TLE. 1 test case gives TLE.I have tri'
en1 Английский Forrest_Gump 2020-11-26 17:21:05 2133 Initial revision (published)