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

### DemonStar's blog

By DemonStar, history, 5 weeks ago, ,

Monsters

How to solve this problem.

• +3

 » 5 weeks ago, # |   +3 Looks like multi-source BFS would help. Run 2 BFS simultaneosuly, one for hero and other for all monsters combined. Delete nodes in hero's graph whenever all monsters take an extra step. If hero's BFS still finds boundary , then he wins. I'll update once I have tried.
•  » » 5 weeks ago, # ^ |   0 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[1001]; 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(); } 
•  » » » 5 weeks ago, # ^ |   0 I have done similar as you said but in cses submission in two testcase it shows UNKNOWN but IDE gives correct answer and in one testcase it gives TLE can you please help me out.my code
•  » » » » 5 weeks ago, # ^ |   0 I think reason for TLE might be ans=perent[x][y]+ans;Try using += and reversing the string
 » 5 weeks ago, # |   0 Interesting the Way I approached it was I enqueued all the monsters positions and did bfs on those and kept the closest distance of any coordinate in the grid in a matrix. Then I just did normal bfs from the start position but had to add a condition that If I am at a cell (i, j) going to a cell(x, y) the distance I travel to (i, j) has to be strictly less than the closest distance from the monsters to (x, y). an interesting problem I saw similiar to this was IOI 2009 Mecho, which was similiar but added another part to the problem my code for the problem is here do note that visited1 is the closest distance to a square from a monster and visited is the closest square from the person https://pastebin.com/GBDJxiFm
•  » » 5 weeks ago, # ^ |   +3 Well, in the end it is the same. All fields are divided into two groups: Fields monsters reach first, and fields hero reach first. We need to find a path using only the fields of the hero group.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 Thanks, I got it.