P3836 [IOI 2017] Nowruz

[Data and checker](http://pan.baidu.com/s/1o8jwPmy) [moved to attachments].

Nowruz (the Persian New Year) is in a few days. Grandfather has invited his whole family to gather in his garden. Among the many guests, there are $k$ children. To make the party more fun for them, Grandfather plans to let them play hide-and-seek. The entire garden can be seen as an $m \times n$ grid of cells. Some cells (possibly none) are blocked by rocks; the remaining cells are called empty cells. If two cells share a side, they are called neighbors. Therefore, each cell has at most $4$ neighbors: two horizontal and two vertical. Grandfather wants to turn the garden into a maze. To do this, he will plant bushes on some empty cells to block them; those cells then cease to be empty. A maze must satisfy the following property: for any pair of empty cells $a$ and $b$, there is exactly one simple path between them. A simple path from $a$ to $b$ is a sequence of distinct cells starting at empty cell $a$ and ending at empty cell $b$, where every two consecutive cells are neighbors. A child can hide in a cell if and only if the cell is empty and it has exactly one empty neighbor. At most one child can hide in a single empty cell. You are given a map of the entire garden. Your task is to help Grandfather construct a maze that allows as many children as possible to hide. # Scoring A valid output file must satisfy all of the following: - Apart from changing any number of `.` characters in the input to `X` (i.e., planting bushes), the output map must be identical to the input map. - The output map must satisfy all the maze properties stated above. For a given testdata, if your output is not valid, your score for this testdata is $0$. Otherwise, your score is $\min(10, 10 \cdot l / k)$, rounded down to two decimal places, where $l$ is the maximum number of children that can hide in your output maze, and $k$ is the number of children specified in the input file. You receive $10$ points for a testdata if and only if your output maze can hide at least $k$ children. For every testdata there exists a solution worth $10$ points. Note: If your output is valid but the above formula still yields a score of $0$, the judging system will display “Wrong Answer”.

This is an output-only problem with partial scoring. There are $10$ input files describing Grandfather’s garden. For each input file, you should submit an output file containing a maze map. Your score is based on the number of children that can hide in the maze you submit for each input file. You do not need to submit any source code. Each input file describes the garden grid and gives the number of invited children $k$, in the following format: Line $1$: $m \ n \ k$. Line $1 + i$ ($1 \leqslant i \leqslant m$): the $i$-th row of the grid, a string of length $n$ with no spaces, consisting of: - `.`: an empty cell, - `#`: a rock.

Line $i$ ($1 \leqslant i \leqslant m$): the $i$-th row of the maze (the garden after planting bushes). It is a string of length $n$ with no spaces, consisting of: - `.`: an empty cell, - `#`: a rock, - `X`: a bush (note that the letter X must be uppercase).

The sample output is one valid output. For this output, since $l = 4$ children can hide in the maze, the score is $10 \cdot 4 / 5 = 8$. The cells where children can hide are marked with `O` below: ```plain OXOX# .#.O# ...#X XX.O# ``` The following three outputs are invalid: ```plain .XXX# ...X# XXXX# .#XX# .#.X# X#XX# ...#. ...#X ..X#X XX..# XXXX# ..XX# ``` In the leftmost output, there is no simple path between the empty cell in the top-left corner and the empty cell in the rightmost column near the bottom-right. In each of the other two outputs, there are two simple paths between some pair of empty cells. # Constraints $1 \leqslant m, n \leqslant 1024$. Translated by ChatGPT 5