Mê Cung

Trong một buổi xem phim về kho báu, FullHouse Dev bị cuốn hút bởi cảnh nhân vật chính phải tìm đường trong mê cung để đến được kho báu. Lấy cảm hứng từ đó, họ quyết định tạo ra một thử thách lập trình về việc tìm đường đi trong mê cung.

Bài toán

FullHouse Dev được cung cấp một bản đồ mê cung và nhiệm vụ là tìm đường đi từ điểm xuất phát đến đích. Họ có thể di chuyển sang trái, phải, lên trên và xuống dưới.

INPUT FORMAT:

• 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 đồ.
• \(n\) dòng tiếp theo, mỗi dòng chứa \(m\) ký tự mô tả mê cung:
  • . (sàn nhà)
  • # (tường)
  • A (điểm xuất phát)
  • B (điểm đích)
• Trong input chỉ có đúng một điểm A và một điểm B.

OUTPUT FORMAT:

• Đầu tiên in ra "YES" nếu tồn tại đường đi, và "NO" nếu không.
• Nếu có đường đi, in ra độ dài của đường đi ngắn nhất và mô tả đường đi bằng một chuỗi các ký tự:
  • L (sang trái)
  • R (sang phải)
  • U (đi lên)
  • D (đi xuống)
• Có thể in ra bất kỳ đáp án hợp lệ nào.

Ràng buộc:

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

Ví dụ

INPUT

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

OUTPUT

YES
9
LDDRRRRRU

Giải thích

Trong ví dụ này, FullHouse Dev tìm được đường đi từ điểm A đến điểm B với độ dài 9 bước. Đường đi được mô tả bằng chuỗi "LDDRRRRRU", tương ứng với các bước di chuyển: sang trái, xuống 2 lần, sang phải 5 lần, và cuối cùng là đi lên.