TLE in Labyrinth(CSES) problem

help
,
1

Problem Link:(CSES - Labyrinth)
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?

2

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";
}
2 Likes
3

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
4

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
5

Okay, thank u so much bro : )

6

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