Description

In biology class, the teacher began introducing cells. To deepen the students’ impression, the teacher defined a kind of cell in an $n \times m$ matrix that contains only the hash # and the dot ..

A cell is composed of a nucleus, cytoplasm, and membrane. The nucleus is a 4-connected (connected via up, down, left, right) connected component consisting entirely of #. It must be solid, i.e., there cannot exist a 4-connected . component that is completely enclosed by it (completely enclosed means that this . component is not adjacent to the matrix border, and all of its 4-neighbor cells belong to the # component that contains it). The membrane is an 8-connected (up, down, left, right, and the 4 diagonal directions) connected component consisting entirely of # that is non-solid. The membrane encloses exactly one 4-connected region, and there is exactly one nucleus inside this region; all other positions in this region are ..

All connected components must be maximal, i.e., for an 8-connected component, there must not exist a # outside that is 8-connected to any # in this component; similarly, for a 4-connected component, there must not exist a # outside that is 4-connected to any # in this component.

Now, the teacher drew a picture and asked Xiao E to determine how many cells are in the picture and to change every # that does not belong to any cell into ..

Input Format

The first line contains two positive integers $n, m$.

Then follows an $n \times m$ character matrix, guaranteed to contain only # and ..

Output Format

The first line contains an integer, the number of cells in the input matrix.

Then output an $n \times m$ character matrix, representing the modified picture according to the requirements.

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

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

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

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

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

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

Hint

For $20\%$ of the testdata, $n, m \le 20$.

For another $20\%$ of the testdata, it is guaranteed that all # belong to some valid cell.

For $100\%$ of the testdata, $1 \le n, m \le 1000$.

Translated by ChatGPT 5