CF1227E Arson In Berland Forest

伯兰德森林可以被表示为一个无限的网格平面。每个格子里都有一棵树。也就是说，在最近的事件发生之前，每个格子都有树。 一场毁灭性的火灾席卷了森林，许多树木因此受损。具体来说，你有一张 $n \times m$ 的矩形地图，表示受损的森林区域。被烧毁的树用 "X" 标记，未受损的树用 "." 标记。你可以确定所有被烧毁的树都在地图上显示。地图外的所有树都是未受损的。 消防员很快扑灭了大火，现在他们正在调查起火原因。主要的猜测是有人纵火：在某一时刻（我们记作 $0$ 时刻），有一些树被点燃。在第 $0$ 分钟开始时，只有最初被点燃的树在燃烧。每过一分钟，在每一棵燃烧的树的 $8$ 个相邻格子的树都会被点燃。在第 $T$ 分钟开始时，大火被扑灭。 消防员想尽快找到纵火者。问题是，他们既不知道 $T$ 的值（火灾持续了多久），也不知道最初被点燃的树的坐标。你的任务是找出最大的 $T$（以便知道纵火者可能逃得多远），以及一种可能的最初被点燃的树的集合。 注意，你需要最大化 $T$ 的值，但最初被点燃的树的集合可以是任意的。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^6$，$1 \le n \cdot m \le 10^6$）——地图的尺寸。 接下来的 $n$ 行描述地图。第 $i$ 行对应地图的第 $i$ 行，包含一个长度为 $m$ 的字符串。第 $i$ 行第 $j$ 个字符为 "X" 表示该位置的树被烧毁，为 "." 表示未受损。 保证地图上至少有一个 "X"。

第一行输出一个整数 $T$，表示森林着火的最长时间。 接下来的 $n$ 行输出一个证明：一张 $n \times m$ 的地图，最初被点燃的树用 "X" 标记，其余用 "." 标记。

由 ChatGPT 4.1 翻译