Lửa lan trong khu rừng
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Một khu rừng được biểu diễn dưới dạng lưới ô vuông kích thước $R \times C$. Mỗi ô là một trong ba loại: . (bãi cỏ), # (vách đá không cháy), hoặc F (điểm đang cháy ban đầu tại thời điểm $0$).
Mỗi phút, ngọn lửa từ một ô đang cháy sẽ lan sang tối đa $4$ ô kề cạnh (trên, dưới, trái, phải) nếu ô đó là bãi cỏ .. Hãy tính thời gian tối thiểu để toàn bộ các ô bãi cỏ trong rừng đều bốc cháy, hoặc cho biết có ô bãi cỏ không bao giờ bị cháy.
Dữ liệu vào
Dòng đầu chứa hai số nguyên $R, C$.
$R$ dòng tiếp theo, mỗi dòng gồm $C$ ký tự thuộc tập {'.', '#', 'F'}.
Dữ liệu ra
In ra số phút tối thiểu để tất cả các ô . đều bị cháy. Nếu tồn tại ít nhất một ô . không thể bị cháy, in ra -1.
Ví dụ
| Input | Output |
|---|---|
| 3 4 F..# ..#. ...F |
2 |
| 3 3 F#. ##. ... |
-1 |
Giới hạn
- $1 \le R, C \le 1000$
Community Discussion