Monsters

Monsters

CSES hard

أنت وبعض الوحوش في متاهة. كلما خطوت خطوة (أعلى أو أسفل أو يسارًا أو يمينًا)، يمكن لكل وحش أن يخطو خطوة في الوقت نفسه. هدفك أن تصل إلى أي مربع على حافة المتاهة دون أن تكون أبدًا في المربع نفسه مع وحش.

هل هذا ممكن؟ إذا كان ممكنًا فأوجد مسارًا. يجب أن ينجح مسارك في كل الحالات، حتى لو عرفته الوحوش مسبقًا.

القيود:

• \(1 \le n, m \le 1000\)

الإدخال:

• السطر الأول: عددان صحيحان \(n\) و \(m\) — ارتفاع الخريطة وعرضها.
• الأسطر الـ \(n\) التالية: في كل سطر \(m\) حرفًا: . (أرضية)، # (جدار)، A (بدايتك)، أو M (وحش). يوجد حرف A واحد بالضبط.

المخرجات:

• YES إذا كان الهدف ممكنًا، وإلا NO.
• إذا كان ممكنًا: طول المسار، ثم المسار نصًّا من الأحرف U و D و L و R. يُقبل أي مسار لا يزيد طوله على \(n \cdot m\).

مثال:

الإدخال:

5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######

المخرجات:

YES
5
RRDDR

الحل

الوحوش تعرف مسارنا، لذلك يجب أن نفترض أن كل وحش يتحرك في أقصر مسار إلى أي مكان نذهب إليه. إذن يكون الدخول إلى مربع في الزمن \(t\) آمنًا فقط إذا لم يستطع أي وحش الوصول إليه في الزمن \(t\) أو قبله. إذا استطاع وحش أن يصل قبلنا، فيمكنه أيضًا أن ينتظرنا هناك.

هذا يعطي تشغيلين للبحث بالعرض (BFS):

1. BFS من كل الوحوش معًا. نضع كل مربعات الوحوش في الطابور بمسافة \(0\) قبل أن يبدأ BFS. عندها monsterDist[r][c] هو أبكر زمن يمكن أن يكون فيه أي وحش في المربع \((r, c)\)، أو \(-1\) إذا لم يستطع أي وحش الوصول إليه.
2. BFS من A، كما في مسألة Labyrinth. ندخل مربعًا مجاورًا في الزمن arrival فقط إذا لم يستطع أي وحش أن يكون فيه في ذلك الزمن: monsterDist يساوي \(-1\) أو أكبر من arrival.

بمجرد أن يأخذ BFS الثاني من الطابور مربعًا على الحافة، نعيد بناء المسار من الاتجاهات المخزّنة، تمامًا كما في Labyrinth. قد يكون مربع البداية نفسه على الحافة؛ عندها الجواب YES بمسار فارغ. إذا فرغ الطابور أولًا فالجواب NO.

يتحرك BFS في أقصر المسارات، لذلك إذا وُجد أي مسار آمن إلى الحافة فإن BFS الثاني يجد واحدًا. يستغرق كل من التشغيلين زمنًا \(O(n \cdot m)\).

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