[SDOI2009]细胞探索

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

12 13
.###..#####..
#...#.#....#.
#.#.#.#..#.#.
#...#..#...#.
.###.#..###..
....#..##...#
..........###
##########..#
#...........#
#.###...###.#
#...........#
#############

输出样例 #1

1
......#####..
......#....#.
......#..#.#.
.......#...#.
........###..
.......##....
.............
.............
.............
.............
.............
.............

输入样例 #2

9 14
#########.....
#.......#....#
#.#####.#...#.
#.#...#.#..#..
#.#.#.#.#.#..#
#.#...#.#..#..
#.#####.#...#.
#.......#....#
#########.....

输出样例 #2

1
..............
..............
..#####.......
..#...#.......
..#.#.#.......
..#...#.......
..#####.......
..............
..............

输入样例 #3

7 15
#######.#######
#.....#.#.....#
#.###.#.#.###.#
#.#.#.#.#.#...#
#.###.#.#.###.#
#.....#.#.....#
#######.#######

输出样例 #3

1
........#######
........#.....#
........#.###.#
........#.#...#
........#.###.#
........#.....#
........#######

说明

对于20%的数据,满足1 ≤ N, M ≤ 20。 另有20%的数据,满足所有“#”都属于某一个正确的细胞。 对于100%的数据,满足1 ≤ N, M ≤ 1,000。