Điểm:
1600 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Bạ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ộtA
trong đầ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
,L
và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 \cdot m\) bước.
Constraints
- \(1 \leq n, m \leq 10 ^ 3\)
Example
Sample input
5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######
Sample output
YES
5
RRDDR
Bình luận
https://ideone.com/OfaydF
tại sao cứ tle 1 test v nhỉ