Fill the Maze
You are given a grid maze with height
h and width w, which has floor cells marked with dots (.) and wall cells marked with hashtags (#). You are asked to mark k floor cells as walls. Yet, you should make sure that the remaining cells still form a connected area and that you don’t accidentally disconnect any part of a maze.It’s guaranteed that the floor cells in the initial maze form a connected area.
Input
The first line of the input contains 3 integers
h, w (1 ≤ h, w ≤ 500), and k (0 ≤ k < n), where n is the number of floor cells in the initial grid.Output
The program should print any valid maze where
k floor cells of the initial grid are marked as walls and there are no disconnected areas in the maze.The newly marked walls should be represented with an
X symbol.Examples
Input
5 4 5
#...
#.#.
.#..
...#
.#.#Output
#XXX
#X#X
.#..
...#
.#.#Input
3 4 2
#..#
..#.
#...Output
#XX#
..#.
#...Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB