Độ khó: Khá (3/4 điểm)

🎓 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

Một trận lũ bất ngờ ập đến vùng đồng bằng. Bản đồ khu vực là một lưới gồm ~N~ hàng và ~M~ cột, mỗi ô là một trong các kí tự:

• . — ô đất trống;
• # — ô đá cao, cả người lẫn nước đều không đi vào được;
• * — ô đang có nước (nguồn lũ), có thể có nhiều ô như vậy;
• S — vị trí hiện tại của thầy Sơn (là ô đất trống);
• E — trạm cứu hộ (là ô đất trống). Thầy Sơn cần đến được ô này.

Thời gian tính theo phút, bắt đầu từ phút ~0~. Trong mỗi phút, lần lượt xảy ra hai việc:

1. Thầy Sơn phải di chuyển sang một trong bốn ô kề cạnh (trên, dưới, trái, phải). Thầy Sơn không được đi ra ngoài bản đồ, không được vào ô đá và không được vào ô đang có nước. Nếu ô thầy Sơn vừa bước vào là E thì thầy Sơn được cứu ngay lập tức.
2. Sau đó, nước tràn từ mỗi ô có nước sang tất cả các ô kề cạnh không phải ô đá. Nếu ô thầy Sơn đang đứng bị nước tràn tới thì thầy Sơn gặp nguy hiểm — thầy Sơn không được phép để chuyện này xảy ra.

Lưu ý:

• Bản đồ có thể không có ô * nào.
• Nước tràn vào cả ô S và ô E như các ô đất trống khác — trạm cứu hộ không chặn được nước.
• Nếu trong cùng một phút thầy Sơn bước vào ô E (việc 1) và nước cũng tràn tới ô E (việc 2), thầy Sơn vẫn được tính là thoát hiểm thành công, vì thầy đã được cứu trước khi nước tới.
• Thầy Sơn được phép đi lại vào ô mình đã đi qua, nhưng không được đứng yên tại chỗ.
• Số phút cần tìm chính là số bước di chuyển của thầy Sơn.

Hãy tính số phút ít nhất để thầy Sơn đến được trạm cứu hộ một cách an toàn, hoặc cho biết điều đó là không thể.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, M~ ~(1 \le N, M \le 1000;\ N \times M \ge 2)~.
• ~N~ dòng tiếp theo, mỗi dòng là một xâu gồm đúng ~M~ kí tự mô tả một hàng của bản đồ. Bản đồ có đúng một kí tự S và đúng một kí tự E.

Kết quả

Một số nguyên duy nhất là số phút ít nhất để thầy Sơn đến được ô E. Nếu không thể, in ra -1.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): bản đồ không có ô nước *.
• Subtask 2 (~30\%~ số điểm): ~N, M \le 50~.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 3 giây.

Sample Input 1

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

Sample Output 1

7

Sample Input 2

4 5
S...#
..*.#
.#...
...#E

Sample Output 2

-1

Sample Input 3

3 5
S...E
####.
..*..

Sample Output 3

4

Giải thích

• Ví dụ 1: không có nước, thầy Sơn đi theo đường ngắn nhất gồm ~7~ bước, chẳng hạn đi hết hàng ~1~ sang phải rồi đi xuống theo cột ~5~.
• Ví dụ 2: nước lan rất nhanh từ ô ở hàng ~2~, cột ~3~ và chặn mọi con đường đến E trước khi thầy Sơn tới nơi.
• Ví dụ 3: Thầy Sơn đi thẳng sang phải ~4~ phút. Nước tới ô E cũng ở phút thứ ~4~, nhưng trong phút đó thầy Sơn di chuyển trước và được cứu ngay khi bước vào E, nên vẫn an toàn.

Nguồn: Đề tự luyện HSG Tin học lớp 9 (đề tự soạn).