Can some one help me undertand why this solution is giving a TLE for a particular test case.

Task :https://cses.fi/problemset/task/1193/

Solution :

**Code**

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
bool inside(ll i, ll j, ll r, ll c)
{
return (i < r && j < c && i >= 0 && j >= 0);
}
pair<ll, ll> directions[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
void solve()
{
int n, m;
cin >> n >> m;
vector<vector<char>> arr(n, vector<char>(m, '#'));
int s1 = -1, s2 = -1;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
cin >> arr[i][j];
if (arr[i][j] == 'A')
{
s1 = i;
s2 = j;
}
}
vector<vector<bool>> vis(n, vector<bool>(m, false));
map<pair<int, int>, char> hash;
hash[{0, 1}] = 'R';
hash[{1, 0}] = 'D';
hash[{0, -1}] = 'L';
hash[{-1, 0}] = 'U';
queue<pair<pair<int, int> , string> > q;
// cout<<s1<<" "<<s2<<endl<<endl;
q.push({{s1, s2} , ""});
vis[s1][s2]= true ;
while (q.empty() == false)
{
auto u = q.front();
q.pop();
for (auto p : directions)
{
int x = p.first + u.first.first;
int y = p.second + u.first.second;
if (inside(x, y, n, m) && vis[x][y] ==false && (arr[x][y] == '.' || arr[x][y] == 'B'))
{
string str = u.second;
str += hash[{p.first, p.second}];
// cout<<x<<":"<<y<<endl;
if (arr[x][y] == 'B')
{
cout << "YES" << endl;
cout << str.length() << endl;
cout << str << endl;
return;
}
// cout << x << ":" << y << endl;
vis[x][y] = true;
q.push({{x, y} , str});
}
}
}
cout << "NO" << endl;
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ull t = 1;
// cin >> t;
// cout << "nooml";
while (t--)
{
solve();
}
}
```

...

TLE test case : https://cses.fi/file/3d5f25fa10486d5059bfe87f28554e8fa18d9e0f1f1d6f27f3d3f3d324ab45f0/1/1/

If i understand your code correctly, you go with bfs and for each cell in the labyrinth you store the path from starting cell to this cell, and in the end you just print path of finishing cell. It will probably use too much memory/time. Instead of it, try to store it's "parent", i.e. the cell, from wich you come to your current cell. This way, you will be able to easily construct your path from finish cell to start, and then just reverse.

Thank you for your response .But i cant understand why my approach would take more time. It does take a lot of memory storing the strings but why time actually. And how would your approach save this time and memory as we are storing the parents which would take memory.

Let's suppose we have 900x900 labyrinth with each cell unlocked, A is in point (0,0) and B is in point (899,899). Storing parents with single char will take 8*900*900=6480000 bits, storing path with your approach will take(let's suppose 900 is average length of string you store) 8*900*900*900=5832000000 bits. My calculations may be a little bit off, but I hope you get the general picture.

Firstly, you could have time and memory limit at the same time, but checker shows only TL because it happens first. Your time complexity in the worst case is O(n^2*log(n)*c) where c is a constant of all your computations, including

`map <pair <int, int>, char>`

finding time, string concatenation(i'm not sure about this, maybe it's even O(length)). O(10^8) ~ 1 second, and your time complexity is O(10^7*c), which is luckily too muchn^2 in time complexity I understand. But the log(n) part??? also n^2 will give only 10^6 worst case. Why 10^7

I understood the correct method, but still confused why my initial one didnt work.

Oh, i thought you were using priority queue instead of queue, but nevermind, it doesn't change anything else.

At least, there is ML error.

Also, I checked your code and it runs in 57 seconds.

I don't know exactly how it works, probably huge amount of memory needs a lot of time to run.

daymn...guess i ll have to avoid using this method anyway.. Thanks

Just stick with the standard BFS always. Store parents no paths

ya