题目描述

有轨电车上总会出现诸多问题，其中包括人群抢夺座位的乱象——他们总会以飞快的速度去抢距离自己最近的座位。

当多名乘客同时瞄准同一个座位准备入座时，问题将会产生。如果只有一名乘客离该座位最近（对于此题，两个点的距离定义为欧几里得距离，即 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$），那么他就会入座而其他乘客将会另选最近的座位；如果多名乘客与座位的欧几里得距离都是最近的，那么将会产生「爆炸事件」。「爆炸事件」后，涉及到的乘客和座位都将会「爆炸」（即后续无需继续考虑）。

给定电车中座位、乘客和地板的 $R \times C$ 地图，用 $\texttt .$ 、$\texttt X$ 和 $\texttt L$ 分别表示地板、乘客和座位。求在所有乘客都落座或「爆炸」和座位被抢光最先发生的一个事件之前，发生了多少次「爆炸事件」。

输入格式

第一行，两个整数 $R,C$。

接下来的 $R$ 行，每行 $C$ 个字符 $\texttt .$ / $\texttt X$ / $\texttt L$。

数据保证，至少存在一个 $\texttt X$ 和一个 $\texttt L$。同时，不存在两个 $\texttt L$ 和某一个 $\texttt X$ 的距离相等的情况。

输出格式

输出「爆炸事件」的次数。

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

1

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

2

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

1

提示

【数据规模与约定】

• 对于 $100\%$ 的数据，$1 \le R,C \le 100$。

【提示与说明】

题目译自 COCI 2009-2010 CONTEST #7 Task 3 BAKICE。

本题分值按 COCI 原题设置，满分 $70$。