Hi everyone, I started solving the CSES problemset. I was on problem 2.Labyrinth of the graph problems (https://cses.fi/problemset/task/1193/)

While my approach was BFS as the other A/Cs. Their implementation used various arrays, while mine used a user-defined struct. I was unable to find any differences in their and mine "approach" as such, just the implementation was different. Is this the reason why I am getting a Time Limit Exceeded error or is there some other issue with my implementation?

My Code:

#include <bits/stdc++.h>
using namespace std;


struct Cell {
	int i;
	int j;
	string steps;	
};

int main() {
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	ll n, m;
	cin >> n >> m;
	char arr[n][m];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	queue<Cell> q;
	bool check = false;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 'A') {
				q.push(Cell{i, j, ""});
				check = true;
				break;
			}
		}
		if (check) {
			break;
		}
	}
	string ans = "";
	int d1[] = {0, 0, 1, -1};
	int d2[] = {1, -1, 0, 0};
	char dir[] = {'R', 'L', 'D', 'U'};
	bool ansfound = false;
	while(!q.empty() && !ansfound) {
		int size = q.size();
//		cout << size << endl;
		for (int i = 0; i < size; i++) {
			Cell cur = q.front();
			q.pop();
			int cur_i = cur.i;
			int cur_j = cur.j;
			string cur_steps = cur.steps;
//			cout << cur_steps << endl;
			arr[cur_i][cur_j] = '#';
			for (int j = 0; j < 4; j++) {
				int new_i = cur_i + d1[j];
				int new_j = cur_j + d2[j];
				if (new_i >= 0 && new_i < n && new_j >= 0 && new_j < m && arr[new_i][new_j] == 'B') {
					ansfound = true;
					ans = cur.steps+dir[j];
					break;
				}
				if (new_i >= 0 && new_i < n && new_j >= 0 && new_j < m && arr[new_i][new_j] == '.') {
					q.push(Cell{new_i, new_j, cur_steps+dir[j]});
				}
			}
			if (ansfound) {
				break;
			}
		}
	}
	if (ans.size() > 0) {
		cout << "YES\n" << ans.size() << "\n" <<  ans << "\n";
	} else {
		cout << "NO\n";
	}
}

Accepted Code:

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second

const int h[] = {1, -1, 0, 0}, v[] = {0, 0, 1, -1};

bool vis[1000][1000];
char c, par[1000][1000], ans[1000000];
int N, M, sx, sy, ex, ey, dist[1000][1000];
queue<pii> Q;


int main(){
    scanf("%d %d", &N, &M);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            scanf(" %c", &c);
            if(c == '#')    vis[i][j] = true;
            else if(c == 'A'){
                sx = i; sy = j;
            } else if(c == 'B'){
                ex = i; ey = j;
            }
        }
    }

    vis[sx][sy] = true;
    Q.push({sx, sy});
    while(!Q.empty()){
        pii P = Q.front(); Q.pop();
        for(int i = 0; i < 4; i++){
            int dx = P.x+h[i];
            int dy = P.y+v[i];
            if(0 <= dx && dx < N && 0 <= dy && dy < M && !vis[dx][dy]){
                if(i == 0)      par[dx][dy] = 'D';
                else if(i == 1) par[dx][dy] = 'U';
                else if(i == 2) par[dx][dy] = 'R';
                else if(i == 3) par[dx][dy] = 'L';
                dist[dx][dy] = dist[P.x][P.y]+1;
                vis[dx][dy] = true;
                Q.push({dx, dy});
            }
        }
    }

    if(!vis[ex][ey]){
        printf("NO\n");
        return 0;
    }

    printf("YES\n%d\n", dist[ex][ey]);
    pii P = {ex, ey};
    for(int i = dist[ex][ey]; i > 0; i--){
        ans[i] = par[P.x][P.y];
        if(ans[i] == 'D')       P = {P.x-1, P.y};
        else if(ans[i] == 'U')  P = {P.x+1, P.y};
        else if(ans[i] == 'R')  P = {P.x, P.y-1};
        else if(ans[i] == 'L')  P = {P.x, P.y+1};
    }
    for(int i = 1; i <= dist[ex][ey]; i++)
        printf("%c", ans[i]);
    printf("\n");
}