Hồ Thiên Nga

View as PDF

Submit solution


Points: 0.39 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Anh Quỳnh bựa đòi add =))
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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.

image

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

Input

  • Dòng đầu tiên chứa ~2~ số ~R~ và ~C~, ~1 \leq R~, ~C \leq 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~.

Output

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

Sample Input

10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L

Sample Output

3

Comments

Please read the guidelines before commenting.



  • 2
    Asamai   commented on July 20, 2022, 5:04 p.m.

    Không biết có phải do test yếu không nhưng mà (những ai chưa AC thì không nên đọc nhé :>)

    Code cũ em nộp trên đây AC nhưng mà khi thử vài test tự sinh với code đó, ví dụ như:

    5 10
    .XXX.X.XXX
    XXXX.X.XXX
    LXXXXLX.XX
    XXXXXXXXXX
    XXXXXX.X.X
    Output đúng: 2
    

    hay

    6 11
    .XXX.XL.XXX
    XXXXXXXXXXX
    X.XXX.XLXXX
    XX.XXX.XXX.
    .X.X.XXX.XX
    XXXXXXXXXXX
    Output đúng: 1
    

    thì lại sai ạ.