CSES - Labyrinth | Mê cung

Xem PDF

Điểm: 1300 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho bản đồ của một mê cung, nhiệm vụ của bạn là tìm ra một đường đi từ vị trí bắt đầu đến vị trí kết thúc. Bạn có thể đi sang trái, phải, lên trên và xuống dưới.

Input

  • Dòng đầu tiên chứa hai số nguyên \(n\)\(m\): chiều cao và chiều rộng của bản đồ.
  • \(n\) dòng tiếp theo, mỗi dòng gồm \(m\) ký tự mô tả mê cung. Mỗi ký tự là . (sàn), # (tường), A (bắt đầu) hoặc B (kết thúc).

Output

  • Đầu tiên in YES nếu tồn tại đường đi và NO nếu ngược lại.
  • Nếu có đường đi, dòng tiếp theo in độ dài của đường đi ngắn nhất. Và dòng cuối in mô tả của đường đi đó dưới dạng một xâu bao gồm các ký tự L (trái), R (phải), U (lên) và D (xuống). Bạn có thể in bất kỳ giải pháp hợp lệ nào.

Constraints

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

Example

Sample input

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

Sample output

YES
9
LDDRRRRRU


Bình luận