P8073 [COCI 2009/2010 #7] BAKICE

Many problems can happen on a tram, including people rushing to grab seats—they always try to take the seat closest to them as fast as possible. When several passengers aim for the same seat at the same time, a problem occurs. If only one passenger is the closest to that seat (in 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 sits down and the other passengers will choose their own closest seats instead. If multiple passengers are tied for being the closest to that seat by Euclidean distance, then an “explosion event” happens. After an “explosion event”, all involved passengers and the seat “explode” (that is, they no longer need to be considered later). You are given an $R \times C$ map of seats, passengers, and floor in the tram, where $\texttt .$ , $\texttt X$ , and $\texttt L$ represent floor, passenger, and seat, respectively. Find how many “explosion events” happen before the first of the following occurs: all passengers have either sat down or “exploded”, or all seats have been taken.

The first line contains two integers $R, C$. The next $R$ lines each contain $C$ characters, each being $\texttt .$ / $\texttt X$ / $\texttt L$. The testdata guarantees that there is at least one $\texttt X$ and at least one $\texttt L$. Also, there is no case where one $\texttt X$ has equal distance to two different $\texttt L$.

Output the number of “explosion events”.

**【Constraints】** - For $100\%$ of the testdata, $1 \le R, C \le 100$. **【Hints and Notes】** **Translated from [COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST #7](https://hsin.hr/coci/archive/2009_2010/contest7_tasks.pdf) _Task 3 BAKICE_.** **The score of this problem follows the original COCI settings, with a full score of $70$.** Translated by ChatGPT 5