Quái Vật

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bạn đang ở trong mê cung $n \times m$ ô cùng với các quái vật. Mỗi bước, bạn di chuyển một ô (lên/xuống/trái/phải), và sau đó mỗi quái vật cũng di chuyển một ô theo hướng tối ưu nhất về phía bạn. Cả bạn và quái vật đều không đi vào tường.

Bạn thoát được nếu đến được ô biên của bản đồ trước khi bất kỳ quái vật nào đến ô đó. Hãy tìm đường thoát.

Dữ liệu vào

Dòng 1: hai số nguyên $n$ và $m$ .
$n$ dòng tiếp theo: mỗi dòng gồm $m$ ký tự — # (tường), . (sàn), A (vị trí ban đầu của bạn), M (quái vật).

Dữ liệu ra

Nếu thoát được: in YES, sau đó in độ dài đường đi, rồi in chuỗi di chuyển (U, D, L, R).
Nếu không thoát được: in NO.

Ràng buộc

$1 \leq n, m \leq 1000$
Độ dài đường đi không vượt quá $n \times m$ .

Ví dụ

Input	Output	Giải thích
5 8 ######## #M..A..# #.#.M#.# #M#..#.. #.######	YES 5 RRDDR	Thoát ra biên phải sau 5 bước.
3 3 ... MAM ...	NO	Không thể thoát.

Bình luận

Không có bình luận tại thời điểm này.