← 返回题目列表

Codeforces · 1227/E

E. Berland 森林纵火案

中文机器翻译题面 查看原题

Berland 森林可以表示为无限的单元平面。每个细胞都包含一棵树。也就是说,包含在最近发生的事件之前。

一场毁灭性的大火席卷了森林,数棵树被烧毁。准确地说,您有一个 $$$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”,所有其他树木被标记为“.”。

示例

输入 #1

3 6
XXXXXX
XXXXXX
XXXXXX

输出 #1

1
......
.X.XX.
......

输入 #2

10 10
.XXXXXX...
.XXXXXX...
.XXXXXX...
.XXXXXX...
.XXXXXXXX.
...XXXXXX.
...XXXXXX.
...XXXXXX.
...XXXXXX.
..........

输出 #2

2
..........
..........
...XX.....
..........
..........
..........
.....XX...
..........
..........
..........

输入 #3

4 5
X....
..XXX
..XXX
..XXX

输出 #3

0
X....
..XXX
..XXX
..XXX