Chạy trốn đám cháy
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Bạn đang ở trong một tòa nhà dạng lưới $R \times C$. Mỗi ô có thể là:
#: tường chắn..: ô trống.J: vị trí ban đầu của bạn (duy nhất).F: một đám cháy (có thể có nhiều đám cháy hoặc không có đám cháy nào).
Mỗi giây, bạn có thể di chuyển sang một ô trống kề cạnh (4 hướng), đồng thời mỗi đám cháy cũng lan sang tất cả các ô trống kề cạnh (không lan qua tường #). Bạn thoát khỏi tòa nhà ngay khi bước tới bất kỳ ô nào nằm trên biên của lưới (tại giây đó, ô biên không được đang cháy hoặc bị cháy cùng lúc bạn bước vào).
Tìm thời gian ngắn nhất để bạn đến được một ô biên an toàn (tính theo số bước di chuyển đến ô biên). Nếu bạn đã ở ô biên thì đáp án là 0. Nếu không thể thoát, in ra IMPOSSIBLE.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $R, C$ ($1 \le R, C \le 1000$).
- $R$ dòng tiếp theo, mỗi dòng gồm $C$ ký tự mô tả lưới.
Dữ liệu ra
- Số bước ít nhất để đến được ô biên an toàn, hoặc
IMPOSSIBLE.
Ví dụ
| Input | Output |
|---|---|
| 4 4 #### #JF# #..# #..# |
2 |
Giới hạn
- $1 \le R, C \le 1000$
Community Discussion