Lửa lan trong khu rừng

General
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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$
Draft saved