Problem Description

Tram cars often encounter various issues, including the chaotic scramble for seats among passengers who always rush at lightning speed to grab the nearest available seat.

Problems arise when multiple passengers target the same seat simultaneously. If only one passenger is closest to the seat (for this problem, the distance between two points is defined as the Euclidean distance, i.e., $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$), then that passenger will take the seat while others will choose another nearest seat. If multiple passengers have the same shortest Euclidean distance to the seat, an "explosion event" will occur. After an "explosion event", the involved passengers and the seat will "explode" (i.e., they will no longer be considered).

Given a $R \times C$ map of the tram car showing seats, passengers, and floor, represented by $\texttt .$ , $\texttt X$, and $\texttt L$ respectively, determine the number of "explosion events" that occur before the earliest of all passengers either sitting down or "exploding" and all seats being taken.

Input Format

The first line contains two integers $R, C$.

The next $R$ lines, each containing $C$ characters $\texttt .$ / $\texttt X$ / $\texttt L$.

It is guaranteed that there is at least one $\texttt X$ and one $\texttt L$. Additionally, there will never be two $\texttt L$s equidistant from any $\texttt X$.

Output Format

Output the number of "explosion events".

Sample Input and Output

Sample Input #1

4 4
.LX.
.X..
....
.L..

Sample Output #1

1

Sample Input #2

4 4
.XLX
.X..
...L
.X..

Sample Output #2

2

Sample Input #3

7 7
...X.X.
XL....L
.......
...L...
.....XL
.......
...X...

Sample Output #3

1

Notes/Hints

[Data Range and Constraints]

• For $100\%$ of the data, $1 \le R, C \le 100$.

[Translation Source]

This problem is translated from COCI 2009-2010 CONTEST #7 Task 3 BAKICE.

This problem is scored according to the original COCI settings, with a maximum score of $70$.

见题面 Input 部分

见题面 Output 部分