P15065 [UOI 2024 II Stage] Mole

经过一番艰苦的研究，Anton 决定去他的乡间别墅放松一下。他有一个美丽的花园，里面种着许多不同的花。但是，糟糕的是，他一到就发现地上有很多洞。是鼹鼠！ 现在，Anton 将手持铁锹等待鼹鼠的出现。鼹鼠可能从任何一个洞里钻出来。Anton 想要选择一个位置，使得在最坏情况下，他跑到鼹鼠那里所需的时间**最短**。 花园可以表示为一个 $n \times m$ 的矩阵，其中 $n$ 是行数，$m$ 是列数。行从上到下编号为 $1$ 到 $n$。列从左到右编号为 $1$ 到 $m$。因此，索引为 $(1;1)$ 的单元格位于左上角。 花园的每个单元格 $a_{i, j}$ 描述了该单元格的状态： - $a_{i, j}$ = $\tt{.}$ —— 该单元格没有花或洞； - $a_{i, j}$ = $\tt{F}$ —— 该单元格有花； - $a_{i, j}$ = $\tt{H}$ —— 该单元格有洞。 Anton 还知道洞的数量不超过 $100$。 作为一个在这些花上投入了大量时间的人，你不忍心践踏它们。因此，你需要找到一条不经过它们的路径。 在任何时刻，Anton 可以从位置 $(x, y)$ 移动到以下任意一个位置：$(x-1,y)$、$(x+1,y)$、$(x,y-1)$、$(x,y+1)$，前提是新位置不包含花且在花园范围内。 请找出所有位置 ($x,y$)，使得 Anton 在最坏情况下跑到鼹鼠那里所需的时间最短。

- 第一行包含两个整数 $n$、$m$（$1 \le n \cdot m \le 2 \cdot 10^5$）——花园的长度和宽度。 - 接下来的 $n$ 行，每行包含 $m$ 个字符——花园的描述。 保证从每个不包含花的单元格出发，可以通过不经过花的单元格到达任何其他不包含花的单元格。 保证至少有一个洞，且花园中洞的数量不超过 $100$。

- 第一行输出一个整数 $x$（$1 \leq x \leq n \cdot m$）——最优位置的数量。 - 接下来的 $x$ 行，每行输出一个等待鼹鼠的最优位置 ($x;y$)（$1 \le x \le n$，$1 \le y \le m$）。 位置可以按任意顺序输出。

:::align{center}  ::: 设 $k$ 为花园中洞的数量。 - （$6$ 分）：$n = 1, m = 2$； - （$9$ 分）：$n = 1$； - （$15$ 分）：$k = 1, n \cdot m \le 5 \cdot 10^3$； - （$22$ 分）：$n \cdot m \le 5 \cdot 10^3$； - （$17$ 分）：$k = 1$； - （$31$ 分）：无额外限制。 翻译由 DeepSeek V3 完成