[SDOI2009]细胞探索

提交提交记录讨论

生物课上，老师开始为同学们介绍细胞。为了加深同学们的印象，老师在一张N×M的矩阵中定义了一种细胞，矩阵中仅有井号“#”和点“.”：细胞由细胞核、细胞质及细胞膜构成。细胞核是一个4连通（上下左右相连）的全为“#”的连通块，它必须实心，即不能存在一个4连通的“.”连通块被其完全包围（所谓完全包围指的是，这个“.”连通块不能位于矩阵边界相邻，且它的4相邻格子均属于包含它的“#”连通块）。细胞膜是一个8连通（上下左右，以及4个对角方向）的全为“#”的非实心连通块。细胞膜仅包围一个4连通的区域，且这个区域内有且仅有一个细胞核，这个区域剩下的位置全为“.”。所有连通块必须极大化，即一个8连通块周围不能找到一个“#”与这个连通块的任意一个“#”8连通；同样，对于一个4连通块周围不能找到一个“#”与这个连通块的任意一个“#”4连通。现在，老师画了一幅图画，并让小E回答图画中一共有几个细胞，并把图画中不属于任何一个细胞的“#”改成“.”。

第一行包含两个用空格分隔的正整数N和M，表示矩阵的高和长。接下来一个N行M列的矩阵，矩阵中仅含井号“#”和点“.”，保证没有多余字符。

第一行包含一个整数，表示输入的矩阵中的细胞数。接下来一个N行M列的矩阵，矩阵中仅含井号“#”和点“.”，表示更改后的图画。

样例输入


			【样例输入1】

12 13

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

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

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

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

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

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

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

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

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

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

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

#############







【样例输入2】

9 14

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

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

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

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

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

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

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

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

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









【样例输入3】

7 15

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

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

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

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

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

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

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

样例输出


			【样例输出1】

1

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

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

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

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

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

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

.............

.............

.............

.............

.............

.............





【样例输出2】

1

..............

..............

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

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

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

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

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

..............

..............







【样例输出3】

1

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

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

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

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

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

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

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



【数据规模和约定】 

对于20%的数据，满足1 ≤ N, M ≤ 20。

另有20%的数据，满足所有“#”都属于某一个正确的细胞。

对于100%的数据，满足1 ≤ N, M ≤ 1,000。

#1235. [SDOI2009]细胞探索

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示