P2156 [SDOI2009] Cell Exploration

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 `.`.

The first line contains two positive integers $n, m$. Then follows an $n \times m$ character matrix, guaranteed to contain only `#` and `.`.

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.

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