C. Төөрдөг байшин (Лабиринт)

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Павалд тэгш өнцөгт төөрдөг байшин таалагддаг. Тэгш өнцөгт төөрдөг байшин нь $n \times m$ хэмжээтэй ба нүд бүр нь хоосон эсвэл ханаар хучигдсан байна.Нэг нүднээс нөгөө нүд рүү шилжих нь энэ 2 нүд нь 2-уулаа хоосон бөгөөд ерөнхий талтай үед л боломжтой.

Павел төгш өнцөгт төөрдөг байшингаа зурсан ба үүний дараагаар аль ч хоосон нүднээс өөр дурын хоосон нүд рүү очих боломжтой байлаа. Павел төөрдөг байшингаа арай цөөхөн ханатай байна гэж үзсэн тул яг $k$ ширхэг хоосон нүднүүдийг ханаар хучихаар болжээ. Гэхдээ үүний дараа аль ч хоосон нүднээс өөр ямар ч хоосон нүдэнд очиж болдог чанар хадгалагдах ёстой.

Оролт

Эхний мөрөнд $n,m,k (1 \le n,m \le 500, 0\le k

Дараагийн $n$ мөр бүр $m$ ширхэг тэмдэгт агуулна. Эдгээр нь анх зурагдсан төөрдөг байшинг тодорхойлох юм. "." нь хоосон мөрийг, "#" нь ханыг төлөөлнө.

Гаралт

Павелийн шаардлагад нийцэж байх шинэ төөрдөг байшинг тодорхойлон $n$ мөр бүрт $m$ ширхэг тэмдэгт хэвлэ. Ханаар хучсан хоосон нүдээ "X" тэмдэглэх ба үлдсэн бүх нүднүүд яг хэвээрээ үлдэх ёстой.

Хариу заавал олдох ба олон боломжит хариу байвал аль нэгийг нь дураар хэвлэхэд хангалттай.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
3 4 2
#..#
..#.
#...
Гаралт
#.X#
X.#.
#...
Оролт
5 4 5
#...
#.#.
.#..
...#
.#.#
Гаралт
#XXX
#X#.
X#..
...#
.#.#
Сэтгэгдлүүдийг ачааллаж байна...