Monsters

Monsters
CSES hard

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), or M (a monster). There is exactly one A.

Output:

  • YES if the goal is possible, otherwise NO.
  • 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:

  1. 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.
  2. BFS from A, as in the problem Labyrinth. We step into a neighboring square at time arrival only if no monster can be there at that time: monsterDist is \(-1\) or larger than arrival.

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