Labyrinth

Labyrinth

CSES easy

أُعطيت خريطة لمتاهة، ومهمتك إيجاد مسار من البداية إلى النهاية. يمكنك المشي يساراً ويميناً وأعلى وأسفل.

المدخل:

• السطر الأول: عددان صحيحان n و m — الارتفاع والعرض.

• ثم n أسطر: كل سطر يحتوي m حرفاً:

  • . أرضية
  • # جدار
  • A البداية
  • B النهاية
    يوجد بالضبط حرف A واحد وحرف B واحد.

المخرجات:

• اطبع "YES" إذا كان هناك مسار، وإلا اطبع "NO".

• إذا كان هناك مسار، اطبع أيضاً:

  • طول أقصر مسار
  • سلسلة تصف المسار باستخدام L, R, U, D
    (أي أقصر مسار مقبول)

القيود:

• 1 ≤ n, m ≤ 1000

مثال:

المدخل:

5 8
########
#.A#...#
#.##.#B#
#......#
########

المخرجات:

YES
9
LDDRRRRRU

Solution

نحتاج أقصر مسار في شبكة غير موزونة (كل حركة تكلفتها 1). هذا بالضبط ما تعطيه BFS.

اعتبر كل خلية مفتوحة عقدة، وتوجد أحرف بين الخلايا المفتوحة المتجاورة (أعلى/أسفل/يسار/يمين). شغّل BFS من A، وخزّن من أين أتينا (أب + حركة)، ثم أعد بناء المسار عندما نصل إلى B.

---

فكرة BFS

نحافظ على:

• dist[r][c] = المسافة من A إلى الخلية (r,c) (-1 يعني غير مُزارة)
• parDir[r][c] = أي حركة استُخدمت للدخول إلى (r,c) من أبيها (واحدة من L,R,U,D)

BFS تستكشف الخلايا بترتيب مسافة متزايدة، لذا أول مرة نصل فيها إلى B تكون مضمونة أنها الأقصر.

---

إعادة بناء المسار

إذا كانت B قابلة للوصول، نرجع للخلف من B إلى A باستخدام parDir:

• إذا كانت parDir[cur] == 'U' فهذا يعني أننا تحركنا للأعلى للوصول إلى cur، إذن الأب يقع صفاً واحداً للأسفل، وهكذا.
• نجمع الحركات ثم نعكسها في النهاية.

---

الجواب النهائي

• إذا كانت dist[B] == -1 → اطبع NO.
• غير ذلك اطبع YES، ثم dist[B]، ثم سلسلة الحركات المُعادة بناؤها.

#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];

    pair<int,int> A{-1,-1}, B{-1,-1};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'A') A = {i, j};
            if (grid[i][j] == 'B') B = {i, j};
        }
    }

    vector<vector<int>> dist(n, vector<int>(m, -1));
    vector<vector<char>> parDir(n, vector<char>(m, 0));

    queue<pair<int,int>> q;
    dist[A.first][A.second] = 0;
    q.push(A);

    // Directions: (dr, dc, moveChar)
    const int dr[4] = {-1, 1, 0, 0};
    const int dc[4] = {0, 0, -1, 1};
    const char mv[4] = {'U', 'D', 'L', 'R'};

    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 (dist[nr][nc] != -1) continue;

            dist[nr][nc] = dist[r][c] + 1;
            parDir[nr][nc] = mv[k];
            q.push({nr, nc});
        }
    }

    if (dist[B.first][B.second] == -1) {
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";
    cout << dist[B.first][B.second] << "\n";

    // Reconstruct path from B back to A
    string path;
    int r = B.first, c = B.second;
    while (!(r == A.first && c == A.second)) {
        char d = parDir[r][c];
        path.push_back(d);

        // Move to parent (reverse the move)
        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 << path << "\n";
    return 0;
}