📖 Bài giảng & lời giải: đây là Bài tập 8 trong bài giảng Thuật toán qua trò chơi 2: Mê cung trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Cho mê cung là lưới $n$ hàng, $m$ cột gồm ô trống ., tường #, đúng một ô S (vị trí của em) và một số ô M là vị trí các con quái vật (có thể không có con nào). Mỗi giây em đi sang một ô chung cạnh không phải tường, các quái vật cũng vậy (quái vật cũng có thể đứng yên).

Quái vật rất thông minh, nên em chỉ an toàn khi bước vào một ô mà em tới sớm hơn hẳn mọi quái vật: gọi $t$ là thời điểm em bước vào ô đó, nếu có một quái vật có thể tới ô đó sau không quá $t$ giây (đi theo đường ngắn nhất qua các ô không phải tường) thì em không được bước vào. Em thoát được khi đứng trên một ô ở biên lưới. Nếu S đã ở biên thì đáp án là $0$.

Hãy tìm số bước ít nhất để thoát.

Dữ liệu vào

• Dòng 1: hai số nguyên $n, m$ ($1 \le n, m \le 1000$).
• $n$ dòng tiếp theo, mỗi dòng là một xâu độ dài $m$ gồm các ký tự ., #, S, M.

Kết quả

In ra số bước ít nhất để thoát, hoặc $-1$ nếu không thể thoát an toàn.

Sample Input

5 7
#######
#S...M#
#.###.#
#.....#
##.####

Sample Output

4