CSES - Monsters | Quái vật
Xem dưới dạng PDFBạn và một số con quái vật đang ở trong một mê cung. Khi đi một bước theo một hướng nào đó trong mê cung, mỗi con quái vật cũng có thể đồng thời đi một bước theo một hướng nào đó. Mục tiêu của bạn là đến một trong những ô vuông ranh giới mà không bao giờ đi vào cùng ô với một con quái vật.
Nhiệm vụ của bạn là tìm hiểu xem mục tiêu của bạn có khả thi hay không, và nếu có, hãy in một đường đi mà bạn có thể đi theo. Kế hoạch của bạn phải hoạt động trong mọi tình huống; ngay cả khi những con quái vật biết trước đường đi của bạn.
Input
- Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): chiều cao và chiều rộng của bản đồ.
- Sau đó, có \(n\) dòng gồm \(m\) ký tự mô tả bản đồ. Mỗi ký tự là
.(sàn),#(tường),A(bắt đầu) hoặcM(quái vật). Có chính xác mộtAtrong đầu vào.
Output
- Trước tiên, hãy in YES nếu mục tiêu của bạn là có thể và NO nếu ngược lại.
- Nếu mục tiêu của bạn là có thể, hãy in ví dụ về đường đi hợp lệ (độ dài của đường đi và mô tả của đường đi bằng cách sử dụng các ký tự
D,U,LvàR). - Bạn có thể in bất kỳ đường đi nào miễn là độ dài của nó nhiều nhất là \(n \times m\) bước.
Constraints
- \(1 \le n,m \le 10^3\)
Example
Sample input
5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######Sample output
YES
5
RRDDR
Nhận xét