#6476. 「ICPC World Finals 2017」复制,复制,复制并变异 Replicate Replicate Rfplicbte

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: tangjz

题目描述

细胞自动制造公司(Automatic Cellular Manufacturing)最近刚刚获得批量生产零件的新工艺专利。它的方法使用到包含两种细胞状态的二维网格,每个单元的细胞要么为空,要么为满。当然,具体的细节是专有的。

最初,网格中的一组单元被填充为需要复制的细胞副本。进过一系列离散的步骤,网格中的每个单元会根据自身及附近的八个单元的状态同步进行细胞状态更新。如果这九个单元中有奇数个位置的细胞是满的,那么这个单元的下一个状态也是满的,否则会是空的。图 1 显示了一个由三个满细胞的单元组成的简单模式在复制过程中的几个步骤。

**图 1.** 复制过程。

然而,一个 bug 已经蛰伏在工艺中了。在每次更新单元状态之后,网格中某一个单元的状态可能自动变化。例如,图 2 显示了可能的变化,其中一个细胞在第一次状态更新后出现了自动变化,另一个细胞在第三次状态更新后出现了自动变化。

**图 2.** 复制过程中的错误。该图对应样例输入 1。

很不幸,最初的细胞模式丢失了,只有(可能受到 bug 影响的)复制结果保留了下来。你能否编个程序确定可能的最小的非空的初始细胞模式来产生给定的最终模式呢?

输入格式

第一行包含两个整数 w (1 \leq w \leq 300) h (1 \leq h \leq 300) ,其中 w h 表示最终模式的边框宽度与高度。

接下来 h 行,每行包含 w 个字符,描述了最终的模式。每个字符要么是 .(表示该单元为空),要么是 #(表示该单元为满)。

保证在第一行、最后一行、第一列、最后一列均存在至少一个单元是满的。

输出格式

输出最小的非空的可能产生最终模式的初始模式,假设每个阶段至多会有一个单元状态自动变化。模式的大小取决于边框内的区域。
如果存在多种可能的最小的非空的初始模式,那么任意一种答案都被视为正确的。
请你使用字符 . 表示空的单元,使用 # 表示满的单元。请你用必须要使用的最小行数和列数来输出这个模式。

样例

样例输入 1

10 10
.#...#...#
##..##..##
##.#.##...
##.#.##...
.#...#####
...##..#.#
......###.
##.#.##...
#..#..#..#
##..##..##

样例输出 1

.#
##

样例输入 2

8 8
##..#.##
#.####.#
.#.#.#..
.##.#.##
.#.#.#..
.##.#.##
#..#.###
##.#.##.

样例输出 2

####
#..#
#.##
###.

样例输入 3

5 4
#....
..###
..###
..###

样例输出 3

#