Giải bài trực tuyến

Hai con thiên nga đang ở trong một cái hồ lớn, nhưng chúng lại đang bị chia cắt bởi băng đóng trong hồ nước. Hồ nước có dạng hình chữ nhật được chia thành R dòng C cột. Một số ô trong hồ bị băng đóng. Mùa xuân tới dần, băng trong hồ tan dần – mỗi ngày băng ở tất cả những ô tiếp xúc với nước đang ấm dần trong hồ (tức là kề cạnh một ô không bị đóng băng) sẽ tan ra.

Ví Dụ

Thiên nga có thể di chuyển tự do ở những ô chứa nước nhưng không thể đi qua những ô bị đóng băng. Bạn hãy tính xem sau bao nhiêu ngày thì đôi thiên nga của chúng ta có thể gặp nhau

Dữ liệu vào

• Dòng đầu tiên chứa 2 số R và C, 1 ≤ R, C ≤ 1500.
• Mỗi dòng trong R dòng tiếp theo chứa C kí tự mô tả hồ nước tại thời điểm hiện tại: '.' (dot) thể hiện 1 ô chứa nước, 'X' thể hiện 1 ô bị đóng băng, và 'L' thể hiện ô có thiên nga. Có chính xác 2 ô chữ L.

Dữ liệu ra

• Một dòng duy nhất chứa số ngày đôi thiên nga có thể gặp nhau.

Input:
   10 2
   .L
   ..
   XX
   XX
   XX
   XX
   XX
   XX
   ..
   .L
Output:
   3