Thoát khỏi khu nguy hiểm

Bối cảnh và bài toán

Một kỹ sư ở ô A trong mê cung. Nhiều vùng nguy hiểm M lan đồng thời mỗi phút sang các ô kề. Kỹ sư cũng đi mỗi phút một ô và chỉ an toàn nếu rời khỏi mê cung trước khi vùng nguy hiểm chạm tới ô mình đứng.

Yêu cầu

Xác định có tồn tại kế hoạch thoát ra một ô biên an toàn hay không.

Input

Dòng đầu n, m; sau đó n dòng gồm '#', '.', 'A', 'M'.

Output

In "YES" nếu có thể thoát an toàn, ngược lại "NO".

Ràng buộc

• 1 <= n,m <= 1000 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

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

Output

YES

Giải thích. So sánh thời gian người đến mỗi ô với thời gian nguy hiểm đến sớm nhất; chỉ đi nếu người đến trước.

Ví dụ 2

Input

3 3
###
#A#
#M#

Output

NO

Giải thích. So sánh thời gian người đến mỗi ô với thời gian nguy hiểm đến sớm nhất; chỉ đi nếu người đến trước.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Monsters. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.