Preencha o Labirinto
É-lhe dado um labirinto em forma de grelha com altura
h e largura w, no qual as células de piso estão indicadas por pontos (.) e as células de parede estão indicadas por sinais de cardinal (#). A tarefa consiste em marcar k dessas células de piso como paredes. No entanto, é essencial garantir que as células restantes continuem a formar uma área conectada e que nenhuma parte do labirinto seja acidentalmente desconectada.Está assegurado que, no labirinto inicial, todas as células de piso formam uma área conectada.
Entrada
A primeira linha da entrada contém 3 inteiros
h, w (1 ≤ h, w ≤ 500) e k (0 ≤ k < n), sendo n o número de células de piso na grelha inicial.Saída
O programa deve imprimir qualquer labirinto válido em que
k células de piso sejam marcadas como paredes, sem introduzir áreas desconectadas dentro do labirinto.As paredes que forem marcadas recentemente devem ser representadas com o símbolo
X.Exemplos
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