Заполним лабиринт
Вам дан сеточный лабиринт высотой
h и шириной w, в котором свободные клетки обозначены точками (.), а клетки-стены — символами решётки (#). Необходимо выбрать k свободных клеток и превратить их в стены, при этом важно сохранить связность оставшихся свободных клеток, чтобы в лабиринте не оказалось изолированных участков.Гарантируется, что изначально все свободные клетки в лабиринте образуют одну связанную область.
Входные данные
Первая строка содержит три целых числа
h, w (1 ≤ h, w ≤ 500) и k (0 ≤ k < n), где n — это количество свободных клеток в исходной сетке.Выходные данные
Программа должна вывести любой корректный вариант лабиринта, где
k свободных клеток исходной сетки обозначены как стены и при этом не возникает разрывов в связной области лабиринта.Новые стены следует обозначать символом
X.Примеры
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