### v_raman's blog

By v_raman, history, 3 weeks ago,

The problem can be found here: https://cses.fi/problemset/result/1045629/

I've been working on this problem for a week now — I have over 20 submissions. With different methods:

I tried passing the path along a node, which has a TLE on test case 13:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define F0R(i, a) for(ll i = 0; i < a; i++)
#define f first
#define s second

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
string ds = "RLDU";

const int mxN = 1e3;
int n, m, si, sj, gi, gj;
string s[mxN];
bool e(int x, int y){
return (x < n && x >= 0 && y < m && y >= 0);
}

void bfs(){
queue<pair<pi, string> > fringe;
fringe.push(make_pair(make_pair(si, sj), ""));
s[si][sj] = '#';
// vector<vi> count(n, vector<int>(m));
while(!fringe.empty()){
pair<pi, string> node = fringe.front();
fringe.pop();
pi pos = node.f;
string path = node.s;
// ++count[pos.f][pos.s];
if(pos.f == gi && pos.s == gj){
cout << "YES\n" << path.length() << "\n" << path << "\n";
// for(int i = 0; i < n; i++){
//   for(int j = 0; j < m; j++) cout << count[i][j];
//   cout << "\n";
// }
return;
}
F0R(i, 4){
int nx = pos.f + dx[i];
int ny = pos.s + dy[i];
if(!e(nx, ny)) continue;
if(s[nx][ny] != '#'){
s[nx][ny] = '#';
fringe.push(make_pair( make_pair(nx, ny), path + ds[i]));
}
}
}
cout << "NO" << "\n";
// for(int i = 0; i < n; i++){
//   for(int j = 0; j < m; j++) cout << count[i][j];
//   cout << "\n";
// }
}

int main() {
// freopen("input.txt", "r", stdin);
ios:: sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
F0R(i, n){
cin >> s[i];
F0R(j, m){
if (s[i][j] == 'A') si = i, sj = j;
if (s[i][j] == 'B') gi = i, gj = j;
}
}

bfs();
return 0;
}


My second approach was to backtrack by storing the direction along the path. This also has TLE on test case 13.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;

template <typename T> void setmax(T& a, const T& b) { if (b > a) a = b; }

#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define F0R(i, a) for(ll i = 0; i < a; i++)
#define f first
#define s second
#define pb push_back
#define sz(a) int((a).size())

const int MOD = 1e9+7; // 998244353;
const int MX = 1000; //
const ll INF = 1e18; //
string ds = "RLUD";
int di[] = {0, 0, -1, 1};
int dj[] = {1, -1, 0, 0};

string maze[MX];
int n, m, si, sj, gi, gj, path[MX][MX];

bool o(int x, int y){
return (x < 0 || x >= n || y < 0 || y >= m);
}

struct node{
int i, j;
};

node init(int i, int j){
return {i, j};
}

void bfs(){
queue<node> q;
q.push(init(si, sj));
maze[si][sj] = '#';
while(!q.empty()){
node nn = q.front();
q.pop();
if(nn.i == gi && nn.j == gj){
cout << "YES\n";
int i = nn.i, j = nn.j;
string out = "";
while(i != si || j != sj){
int k = path[i][j];
out = ds[k] + out;
i-= di[k];
j-= dj[k];
}
cout << sz(out) << "\n" << out << "\n";
return;
}
for(int k = 0; k < 4; k++){
int ni = nn.i + di[k];
int nj = nn.j + dj[k];
if(!o(ni, nj) && maze[ni][nj] != '#'){
maze[ni][nj] = '#';
q.push(init(ni, nj));
path[ni][nj] = k;
}
}
}
cout << "NO" << "\n";
}

int main() {
ios_base::sync_with_stdio(0); cin.tie(0); // see Fast Input & Output
cin >> n >> m;
F0R(i, n){
cin >> maze[i];
F0R(j, m){
if (maze[i][j] == 'A') si = i, sj = j;
else if (maze[i][j] == 'B') gi = i, gj = j;
}
}
bfs();
}


I'm lost at this point. What else can I do to optimize in this problem?

• 0

 » 3 weeks ago, # |   0 Your problem is in this line: out = ds[k] + out; What this is doing is reconstructing your "out" string every time you add a character at the start. Instead, add the letter to the end of the string, and after reconstructing the whole path, reverse the string. Fixed code while(i != si || j != sj){ int k = path[i][j]; out.push_back(ds[k]); i-= di[k]; j-= dj[k]; } reverse(out.begin(), out.end()); cout << sz(out) << "\n" << out << "\n"; return; } 
•  » » 3 weeks ago, # ^ |   0 Thank you!