Cuộc hội ngộ của 2 chú ếch

Xem dạng PDF

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:
stolen
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