Mô tả bài toán: Trốn thoát khỏi mê cung

Bạn và một số quái vật đang ở trong một mê cung. Khi bạn thực hiện một bước đi về hướng nào đó trong mê cung, mỗi quái vật cũng có thể di chuyển một bước theo bất kỳ hướng nào. Mục tiêu của bạn là đến được một ô biên của mê cung mà không bao giờ chia sẻ cùng một ô với quái vật.

Nhiệm vụ của bạn là:

1. Xác định liệu bạn có thể đạt được mục tiêu hay không.
2. Nếu có thể, đưa ra một lộ trình để đạt được mục tiêu. Lộ trình của bạn phải hoạt động trong mọi tình huống, kể cả khi quái vật biết trước đường đi của bạn.

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 gồm m ký tự mô tả bản đồ:
  • .: ô trống (có thể đi qua).
  • #: tường (không thể đi qua).
  • A: vị trí bắt đầu của bạn (chỉ xuất hiện một lần).
  • M: vị trí của quái vật.

Output:

• Nếu bạn có thể đạt được mục tiêu, in "YES", sau đó in số bước trên đường đi và một chuỗi gồm các ký tự D (Down), U (Up), L (Left), R (Right) biểu diễn lộ trình.
• Nếu không thể đạt được mục tiêu, in "NO".

Ràng buộc:

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

Ví dụ:

Input:

5 8
########
#M..A..#
#.###.M#
#M#....#
#.###### 

Output:

YES
5
RRDDR