Labyrinth

Labyrinth

CSES easy

You are given a map of a labyrinth, and your task is to find a path from start to end. You can walk left, right, up and down.

Input:

• First line: integers n and m — height and width.

• Next n lines: each has m characters:

  • . floor
  • # wall
  • A start
  • B end There is exactly one A and one B.

Output:

• Print "YES" if there is a path, otherwise print "NO".

• If there is a path, print:

  • the length of the shortest path
  • a string describing the path using L, R, U, D (any shortest path is acceptable)

Constraints:

• 1 ≤ n, m ≤ 1000

Example:

Input:

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

Output:

YES
9
LDDRRRRRU

Solution

We need the shortest path in an unweighted grid (each move costs 1). This is exactly what BFS gives.

Treat each open cell as a node, edges between neighboring open cells (up/down/left/right). Run BFS from A, store where we came from (parent + move), and reconstruct the path when we reach B.

BFS idea

Maintain:

• dist[r][c] = distance from A to cell (r,c) (-1 means unvisited)
• parDir[r][c] = which move was used to enter (r,c) from its parent (one of L,R,U,D)

BFS explores cells in increasing distance, so the first time we reach B is guaranteed to be shortest.

Path reconstruction

If B is reachable, we walk backwards from B to A using parDir:

• If parDir[cur] == 'U', it means we moved up to reach cur, so the parent is one row below, etc.
• Collect moves, reverse at the end.

Final answer

• If dist[B] == -1 → print NO.
• Else print YES, then dist[B], then the reconstructed move string.

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