Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### DemonStar's blog

By DemonStar, history, 5 weeks ago, , Monsters cses, Comments (7)
•  » » Using similar approach as mentioned above Spoiler#include using namespace std; #define vec vector #define pb push_back #define s(x) scanf("%d", &x) #define all(x) x.begin(), x.end() #define pii pair #define fi first #define se second #define mod 1000000007 #define SZ 200005 #define endl "\n" #define trace(x) cerr << #x << ": " << x << endl #define boost ios::sync_with_stdio(0); cin.tie(0) int n, m, x; string grid; pii hero_pos; int di[] = {-1, 0, +1, 0}; int dj[] = {0, +1, 0, -1}; queue hero; queue monsters; vec< vec > dm(1001, vec (1001, -1)); //monster distances vec< vec > dh(1001, vec (1001, -1)); //hero distances /////////////////////////////////////////////////////////////// bool valid(int i, int j) { return i >= 0 and i < n and j >= 0 and j < m and grid[i][j] != '#'; } void initialise_monsters_distance() { while (!monsters.empty()) { pii popped = monsters.front(); int ui = popped.fi; int uj = popped.se; monsters.pop(); for (int k = 0; k < 4; k++) { int vi = ui + di[k]; int vj = uj + dj[k]; if (valid(vi, vj) and dm[vi][vj] == -1) { dm[vi][vj] = dm[ui][uj] + 1; monsters.push({vi, vj}); } } } } pii hero_can_reach() { while (!hero.empty()) { pii popped = hero.front(); int ui = popped.fi; int uj = popped.se; if (ui == 0 || uj == 0 || ui == n - 1 || uj == m - 1) return {ui, uj}; hero.pop(); for (int k = 0; k < 4; k++) { int vi = ui + di[k]; int vj = uj + dj[k]; if (valid(vi, vj) and dh[vi][vj] == -1 and (dm[vi][vj] == -1 || dh[ui][uj] + 1 < dm[vi][vj])) { dh[vi][vj] = dh[ui][uj] + 1; hero.push({vi, vj}); } } } return {-1, -1}; } void printPath(pii final) { vec path; char dir[] = {'D', 'L', 'U', 'R'}; while (final != hero_pos) { for (int k = 0; k < 4; k++) { int vi = final.fi + di[k]; int vj = final.se + dj[k]; pii next = {final.fi + di[k], final.se + dj[k]}; if(valid(vi, vj) and dh[final.fi][final.se] == 1) { if(next == hero_pos) { path.pb(dir[k]); final = next; break; } continue; } if(valid(vi, vj) and dh[vi][vj] == dh[final.fi][final.se]-1) { path.pb(dir[k]); final = next; break; } } } reverse(all(path)); cout << path.size() << endl; for(char dir: path) { cout << dir; } } void purple() { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> grid[i]; } for(int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 'A') { hero_pos = {i, j}; hero.push({i, j}); dh[i][j] = 0; } else if (grid[i][j] == 'M') { monsters.push({i, j}); dm[i][j] = 0; } } } initialise_monsters_distance(); pii final = hero_can_reach(); if(final.fi == -1) { cout << "NO"; return; } cout << "YES\n"; printPath(final); } signed main() { boost; int t = 1; // cin>>t; while (t--) purple(); } 
•  » » » » I think reason for TLE might be ans=perent[x][y]+ans;Try using += and reversing the string