Gửi bài giải
Điểm:
0,40 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C++, Pascal, Python
Có 2 vợ chồng nhà ếch nọ bị chia cắt nhau sau khi Cirno đóng băng Hồ Sương Mù. Hồ có thể được thể hiện bằng một hình chữ nhật có ~N~ dòng và ~M~ cột. Một số ô đã bị đóng băng bởi Cirno được thể hiện bằng kí tự ~'X'~, ô không bị đóng băng là thể hiện bằng kí tự ~'.'~ và vị trí 2 chú ếch là kí tự ~'L'~.
Cứ mỗi ngày qua đi những ô bị đóng băng mà kề với ô chứa nước sẽ tan ra. Những chú ếch có thể di chuyển vào những ô không bị đóng băng. Hãy cho biết sau tối thiểu bao nhiêu ngày thì 2 vợ chồng được đoàn tụ.
Input
- Dòng đầu tiên gồm 2 số tự nhiên ~1 \le N, M \le 1500~.
- Mỗi dòng trong ~N~ dòng tiếp theo gồm ~M~ kí tự mô tả hồ nước.
Output
- Số ngày tối thiểu để 2 vợ chồng ếch gặp nhau.
Sample Input
10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L
Sample Output
3