Riempi il labirinto
Vi viene fornito un labirinto a griglia con altezza
h e larghezza w, che presenta celle del pavimento contrassegnate da punti (.) e celle muro contrassegnate da cancelletto (#). Vi viene richiesto di trasformare k di queste celle del pavimento in muri. Tuttavia, dovete assicurarvi che le celle rimanenti continuino a formare un’unica area connessa e che non si verifichino separazioni accidentali all’interno del labirinto.Si garantisce che, nel labirinto iniziale, tutte le celle di pavimento siano già collegate tra loro in un’unica componente connessa.
Input
La prima riga dell’input contiene 3 interi
h, w (1 ≤ h, w ≤ 500) e k (0 ≤ k < n), dove n è il numero totale di celle di pavimento nella griglia iniziale.Output
Il programma deve stampare un labirinto valido in cui
k celle di pavimento della griglia iniziale vengano contrassegnate come muri, garantendo che nel risultato non siano presenti zone disconnesse.I nuovi muri devono essere indicati con il simbolo
X.Esempi
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