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");
}
