CSES 1193 ↗

Labyrinth

A shortest path from `A` to `B` through floor squares, as a move string.

14
submissions
0.927
best score

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

The first input line has two integers n and m: the height and width of the map.

Then there are n lines of m characters describing the labyrinth. Each character is . (floor), # (wall), A (start), or B (end). There is exactly one A and one B in the input.

Output

First print "YES", if there is a path, and "NO" otherwise.

If there is a path, print the length of the shortest such path and its description as a string consisting of characters L (left), R (right), U (up), and D (down). You can print any valid solution.

Constraints

  • 1≤n,m≤1000

Example

Input:

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

Output:

YES
9
LDDRRRRRU

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/Labyrinth/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Gas

total gas over the tests, across qualifying submissions
leader
556,221,3081,736,460,470

14 qualifying submissions. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

14 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj000.927556,221,308talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-23 03:26 UTC
2lukerj000.902719,302,629talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 22:16 UTC
3lukerj000.895683,355,798talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-23 07:53 UTC
4lukerj000.882630,077,808talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-24 02:39 UTC
5lukerj000.882731,139,424talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-24 05:46 UTC
6lukerj000.874669,641,405talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-22 00:30 UTC
7lukerj000.868763,110,033talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 20:25 UTC
8lukerj000.830944,417,102talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-22 21:46 UTC
9lukerj000.829855,180,130talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-21 21:18 UTC
10lukerj000.828858,203,384talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-24 00:28 UTC
11lukerj000.8271,109,434,099talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-24 10:55 UTC
12lukerj000.814936,723,433talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-23 22:58 UTC
13lukerj000.7611,199,103,176talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-24 06:48 UTC
14lukerj000.6881,736,460,470talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-22 05:39 UTC

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.