Bờm rất yêu thích loài nhím nên trong vườn nhà có nuôi rất nhiều nhím và đặt nhiều chậu đựng thức ăn cho chúng. Các chú nhím của Bờm có tốc độ di chuyển như nhau và chúng đều biết vị trí của các chậu thức ăn. Khi được cho ăn, các chú nhím luôn chọn ăn ở chậu thức ăn gần nhất. Nếu chúng nhận thấy chậu thức ăn gần nhất có khả năng có nhím khác đến ăn trước thì chúng sẽ chọn chậu thức ăn gần nhất kế tiếp. Vấn đề xày ra là khi có hai con nhím hoặc nhiều hơn cùng đến một chậu thức ăn. Các con nhím nãy sẽ đánh nhau làm vỡ chậu đựng thức ăn và sau đó chết hết.
Khu vườn được xem như là một lưới các ô vuông gồm ~R~ dòng và ~C~ cột. Các dòng của lưới được đánh số từ ~1~ đến ~R~, từ trên xuống dưới. Các cột của lưới được đánh số từ ~1~ đến ~C~, từ trái sang phải. Ô năm trên hàng giao của dòng ~i~ và cột ~j~ được gọi là ô ~(i, j)~. Trên mỗi ô ghi một trong ba kí tự:
X
là ô có một con nhím.L
là ô có chậu thức ăn..
là đất vườn.
Khoảng cách giữa hai ô là khoảng cách Euclid. Gọi ~T~ là khoảng cách Euclid giữa ô ~(i, j)~ và ô ~(u, v)~ thì ~T~ = ~\sqrt{(i-u)^{2} + (j-v)^{2}}~.
Yêu cầu: Hãy cho biết có bao nhiêu chậu thức ăn bị vỡ khi Bờm cho nhím ăn.
Dữ liệu vào:
- Dòng thứ nhất chứa hai số nguyên ~R~ và ~C~ ~(1 \le R, C \le 100)~, là số dòng và số cột của lưới, các số trên một dòng cách nhau ít nhất một dấu cách.
- ~R~ dòng tiếp theo, mỗi dòng là một xâu ~C~ kí tự, gồm các kí tự
.
,X
,L
.
Dữ liệu vào luôn có ít nhất một kí tụ X
và một kí tự L
. Dữ liệu cũng đảm bảo không có hai ô L
có cùng khoảng cách đến ô X
.
Kết quả ra
- Xuất ra màn hình một số nguyên, là số chậu thức ăn bị vỡ.
Ví Dụ
Dữ liệu vào
4 4
.XLX
.X..
...L
.X..
Dữ liệu ra
2
Comments