Monsters
You and some monsters are in a labyrinth. Whenever you take a step (up, down, left, or right), each monster may also take one step at the same time. Your goal is to reach any boundary square of the labyrinth without ever being in the same square as a monster.
Is it possible? If yes, find a path. Your path must work in every case, even if the monsters know it in advance.
Constraints:
- \(1 \le n, m \le 1000\)
Input:
- First line: two integers \(n\) and \(m\) — the height and the width of the map.
- Next \(n\) lines: \(m\) characters each:
.(floor),#(wall),A(your start), orM(a monster). There is exactly oneA.
Output:
YESif the goal is possible, otherwiseNO.- If it is possible: the length of a path, and then the path as a string of the characters
U,D,L,R. Any path of length at most \(n \cdot m\) is accepted.
Example:
Input:
5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######
Output:
YES
5
RRDDR
Solution
The monsters know our path, so we must assume that every monster moves along a shortest path to wherever we go. A square is therefore safe to enter at time \(t\) only if no monster can reach it at time \(t\) or earlier. If a monster can arrive earlier, it can also wait there for us.
This gives two BFS runs:
- BFS from all monsters at once. We put every monster square into the queue with distance \(0\) before the BFS starts. Then
monsterDist[r][c]is the earliest time any monster can be in the square \((r, c)\), or \(-1\) if no monster can reach it. - BFS from
A, as in the problem Labyrinth. We step into a neighboring square at timearrivalonly if no monster can be there at that time:monsterDistis \(-1\) or larger thanarrival.
As soon as the second BFS takes a boundary square from the queue, we reconstruct the path with the stored directions, exactly as in Labyrinth. The start square itself can be on the boundary; then the answer is YES with an empty path. If the queue becomes empty first, the answer is NO.
BFS moves along shortest paths, so if any safe path to the boundary exists, the second BFS finds one. Both BFS runs take \(O(n \cdot m)\) time.
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> grid(n);
for (int i = 0; i < n; i++) cin >> grid[i];
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};
const char mv[4] = {'U', 'D', 'L', 'R'};
// 1) BFS from all monsters at once: the earliest time a monster can be in each cell
vector<vector<int>> monsterDist(n, vector<int>(m, -1));
queue<pair<int, int>> q;
pair<int, int> A;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 'M') {
monsterDist[i][j] = 0;
q.push( {i, j});
}
if (grid[i][j] == 'A') A = {i, j};
}
}
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int k = 0; k < 4; k++) {
int nr = r + dr[k];
int nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
if (grid[nr][nc] == '#') continue;
if (monsterDist[nr][nc] != -1) continue;
monsterDist[nr][nc] = monsterDist[r][c] + 1;
q.push( {nr, nc});
}
}
// 2) BFS from A: enter a cell only if we arrive strictly before every monster
vector<vector<int>> dist(n, vector<int>(m, -1));
vector<vector<char>> parDir(n, vector<char>(m, 0));
dist[A.first][A.second] = 0;
q.push(A);
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
if (r == 0 || r == n - 1 || c == 0 || c == m - 1) {
// a boundary cell: reconstruct the path back to A
string path;
while (!(r == A.first && c == A.second)) {
char d = parDir[r][c];
path.push_back(d);
if (d == 'U') r += 1;
else if (d == 'D') r -= 1;
else if (d == 'L') c += 1;
else if (d == 'R') c -= 1;
}
reverse(path.begin(), path.end());
cout << "YES\n";
cout << path.size() << "\n";
cout << path << "\n";
return 0;
}
for (int k = 0; k < 4; k++) {
int nr = r + dr[k];
int nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
if (grid[nr][nc] == '#') continue;
if (dist[nr][nc] != -1) continue;
int arrival = dist[r][c] + 1;
if (monsterDist[nr][nc] != -1 && monsterDist[nr][nc] <= arrival) continue;
dist[nr][nc] = arrival;
parDir[nr][nc] = mv[k];
q.push( {nr, nc});
}
}
cout << "NO\n";
}