Mô tả bài toán:

Bạn được cung cấp một bản đồ của mê cung, nhiệm vụ của bạn là tìm một đường đi ngắn nhất từ điểm bắt đầu ~ A ~ đến điểm kết thúc ~ B ~. Bạn có thể di chuyển theo 4 hướng: trái, phải, lên, xuống.

Input:

• Dòng đầu tiên chứa hai số nguyên ~ n ~ và ~ m ~: chiều cao và chiều rộng của bản đồ.
• Sau đó, có ~ n ~ dòng, mỗi dòng chứa ~ m ~ ký tự mô tả mê cung:
  • .: đại diện cho sàn (nơi bạn có thể đi qua).
  • #: đại diện cho tường (không thể đi qua).
  • A: điểm bắt đầu.
  • B: điểm kết thúc.

Output:

• Nếu có đường đi từ ~ A ~ đến ~ B ~, in ra:

  • "YES" (có đường đi).
  • Chiều dài của đường đi ngắn nhất.
  • Chuỗi mô tả đường đi ngắn nhất, bao gồm các ký tự:
  • L (trái), R (phải), U (lên), D (xuống).

• Nếu không có đường đi, in ra "NO".

Ràng buộc:

• ~ 1 \leq n, m \leq 1000 ~

Ví dụ:

Input:

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

Output:

YES
9
LDRRRRRRU