📖 Bài giảng & lời giải: đây là Bài tập 3 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 # và đúng một ô xuất phát S (là ô trống). Bên ngoài lưới là khoảng trống tự do. Mỗi bước em đi sang một ô chung cạnh không phải tường. Từ một ô trống nằm ở biên lưới (hàng đầu, hàng cuối, cột đầu hoặc cột cuối), bước thêm một bước ra ngoài lưới là thoát.

Hãy tìm số bước ít nhất để thoát ra ngoài (tính cả bước cuối cùng bước ra khỏi lưới).

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.

Kết quả

In ra số bước ít nhất để thoát, hoặc $-1$ nếu bị nhốt.

Sample Input

4 5
#####
#S..#
#.#..
###.#

Sample Output

5