TLE in Labyrinth(CSES) problem

Problem Link:(https://cses.fi/problemset/task/1193)
My solution:(https://cses.fi/paste/aa91e959b18b0063107ccd)

I use BFS to solve this problem, but in some test cases, it is giving TLE. I have no idea why it is showing TLE, as Time Complexity of my solution is O(n*m) where 1<=n<=1000,1<=m<=1000. I try to make my code more readable and clean. Can anyone help me, what I am missing here?

Bro, you are getting a TLE cause you are using maps for storing distances instead of 2-D arrays try replacing it, that’ll work.
Just a suggestion, in case you are not aware you can implement your solution in a more elegant and efficient fashion by using a standard trick for grid problems used in the code attached you can check it out if you want

CODE
#include <bits/stdc++.h>
#define ar array
using namespace std;
const int mxN =1e3+2;
const int di[4]={1,0,-1,0},dj[4]={0,1,0,-1};
const char dc[4]={'D','R','U','L'} ;
int n,m,si,sj,ti,tj,d[mxN][mxN];
string s[mxN],p[mxN] ;
bool e(int i,int j){
  return (i<n&&i>=0&&j<m&&j>=0&&s[i][j]=='.') ;
}
signed main() {
  cin >> n >> m ;
  for(int i=0;i<n;i++)
    cin >> s[i] ; 
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(s[i][j]=='A')
        si=i,sj=j,s[i][j]='.';
      if(s[i][j]=='B')
        ti=i,tj=j,s[i][j]='.';
    }
    p[i]=string(m,0) ;
  }
  queue<ar<int,2>>qu ;
  qu.push({si,sj}) ;
  while(!qu.empty()){
    ar<int,2>u = qu.front();
    qu.pop() ;
    for(int k=0;k<4;k++){
      int ni=u[0]+di[k],nj=u[1]+dj[k];
      if(!e(ni,nj))
        continue ;
      qu.push({ni,nj});
      s[ni][nj]='#';
      d[ni][nj]=k ;
      p[ni][nj]=dc[k] ;
    }
  }
  if(p[ti][tj]){
    string t ;
    cout << "YES"<< endl ;
    while(si^ti || sj^tj){
      t+=p[ti][tj] ;
      int dd=d[ti][tj]^2;
      ti+=di[dd];
      tj+=dj[dd];
    }
    reverse(t.begin(),t.end());
    cout << t.size() <<"\n";
    cout << t ;
  }
  else
    cout << "NO";
}
1 Like

Thankyou so much, yeah it’s work and thanks for suggestion : ).
But I have a doubt, Is map of (pair<int,int>,int) is too slow? Isn’t it just O(logn) for lookup? or am i missing something?

1 Like

Yeah, it is O(logn) theoretically but in my opinion it the data stored in each node of the BST is comparatively higher may that’s why the map under performs in these situations though I am not sure somebody can correct me if I’m wrong. So its recommended going with 2-D arrays as far as possible

1 Like

Okay, thank u so much bro : )

What’s wrong with this solution? Giving WA for few test cases. Can anyone help please?
https://cses.fi/paste/d1cdee77e947f8bc10a1bd/