Ալգորիթմներ և Տվյալների Կառուցվածքներ

Լրացրեք լաբիրինթը

Ձեզ ներկայացվում է բարձրությունը 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

To check your solution you need to sign in
Sign in to continue