问题 5544 --病毒溯源

5544: 病毒溯源

时间限制: 2 Sec  内存限制: 512 MB
提交: 8  解决: 6
[提交][状态][命题人:]

题目描述

典型球状病毒在人群中开始扩散,现在,你需要进行一个溯源工作。

感染者的分布情况可以简化为一个 n 行 m 列的方格图,每个方格上有一个人,人不会离开他所在的位置。用字符 'X' 表示被感染了,字符 '.' 表示未被感染。方格图外的人均未被感染

初始,有一些人因为各种原因被感染了。若一个人被感染了,则第二天会使得其周围 8 个相邻的其他人也被感染。

现在你知道了当前每个人是否感染的情况,求出现最早的感染者的可能是几天前,并求出任意一种可能的最早的感染者分布情况。

输入

第一行包含两个正整数 n,m (1≤n≤10^6, 1≤n·m≤10^6) ,表示方格图的行列数。
接下来 n 行,每行包含 m 个字符。表示地图信息。
保证至少有一个 'X' 。

输出

第一行输出一个整数 T ,表示可能的最早出现感染者时间是 T 天前。
接下来输出 n·m 大小的方格图,表示 T 天可能的感染者分布情况。
样例输入
Copy
样例1:
3 6
XXXXXX
XXXXXX
XXXXXX

样例2:
10 10
.XXXXXX...
.XXXXXX...
.XXXXXX...
.XXXXXX...
.XXXXXXXX.
...XXXXXX.
...XXXXXX.
...XXXXXX.
...XXXXXX.
..........

样例3:
4 5
X....
..XXX
..XXX
..XXX
样例输出
Copy
样例1:
1
......
.X.XX.
......

样例2:
2
..........
..........
...XX.....
..........
..........
..........
.....XX...
..........
..........
..........

样例3:
0
X....
..XXX
..XXX
..XXX

提示

来源

[提交][状态]