Remplir le labyrinthe
On vous donne une grille de hauteur
h et de largeur w, dont les cellules de sol sont représentées par des points (.) et les cellules de mur par des dièses (#). Vous devez désigner k cellules de sol comme murs. Cependant, il est impératif que les cellules restantes demeurent connectées et que vous n’isoliez aucune partie du labyrinthe.Il est garanti que, dans la grille initiale, toutes les cellules de sol forment une zone connectée.
Entrée
La première ligne de l’entrée contient 3 entiers
h, w (1 ≤ h, w ≤ 500) et k (0 ≤ k < n), où n correspond au nombre de cellules de sol dans la grille initiale.Sortie
Le programme doit afficher un labyrinthe valide où
k cellules de sol de la grille initiale sont désignées comme murs, de sorte qu’il n’existe aucune zone déconnectée.Les nouveaux murs doivent apparaître avec le symbole
X.Exemples
Entrée
5 4 5
#...
#.#.
.#..
...#
.#.#Sortie
#XXX
#X#X
.#..
...#
.#.#Entrée
3 4 2
#..#
..#.
#...Sortie
#XX#
..#.
#...Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB