A93058.「SDOI2009」细胞探索
省选/NOI-
官方
通过率：0%
时间限制：1.00s
内存限制：125MB
题目描述
生物课上，老师开始为同学们介绍细胞。为了加深同学们的印象，老师在一张 N×M 的矩阵中定义了一种细胞，矩阵中仅有井号 # 和点 .：
细胞由细胞核、细胞质及细胞膜构成。细胞核是一个 4 连通（上下左右相连）的全为 # 的连通块，它必须实心，即不能存在一个4连通的 . 连通块被其完全包围（所谓完全包围指的是，这个 . 连通块不能位于矩阵边界相邻，且它的 4 相邻格子均属于包含它的 # 连通块）。细胞膜是一个 8 连通（上下左右，以及 4 个对角方向）的全为 # 的非实心连通块。细胞膜仅包围一个 4 连通的区域，且这个区域内有且仅有一个细胞核，这个区域剩下的位置全为 .。
所有连通块必须极大化，即一个 8 连通块周围不能找到一个 # 与这个连通块的任意一个 # 8 连通；同样，对于一个 4 连通块周围不能找到一个 # 与这个连通块的任意一个 # 4 连通。
现在，老师画了一幅图画，并让小 E 回答图画中一共有几个细胞，并把图画中不属于任何一个细胞的 # 改成.。
输入格式
第一行包含两个用空格分隔的正整数 N 和 M，表示矩阵的行数和列数。
接下来一个 N 行 M 列的矩阵，矩阵中仅含井号 # 和点 .，保证没有多余字符。
输出格式
第一行包含一个整数，表示输入的矩阵中的细胞数。
接下来一个 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≤1000。