Problem T
L lyklar
Þig vantar að komast inn í læsta skrá með ansi undarlegt lyklakerfi. Í raun má búa til skráarlás úr hvaða $\mathcal{NP}$-verkefni sem er, og höfundur skrárnar virðist hafa ætlað að sýna að svo sé virkilega raunin.
Þegar þú reynir að opna skrána sýnir það þér pixlað form sem fylla þarf af L-laga kubbum. Þú veist auðvitað að það að reyna finna leið til að fylla formið af þessum kubbum er $\mathcal{NP}$-hard verkefni, svo þú þarft einhverjar frekari upplýsingar til að þetta sé yfir höfuð fýsilegt.
Einverju síðar tekst þér að sjá að tíminn sem það tekur kerfið að gá hvort lausnin þín sé gild er ekki alveg fastur. Út frá þessu tekst þér að finna að það sé háð fjölda hornreita á réttum stað, svo þér tekst að ákvarða hvar hornin á öllum kubbunum eiga að vera. Dugar þetta til að leysa verkefnið?
Inntak
Fyrsta lína inntaksins inniheldur tvær heiltölur $1 \leq R, C \leq 512$. Næst fylgja $R$ línur, hver með $C$ stöfum, sem lýsa forminu sem þarf að þekja með L-laga kubbum. Stafurinn . táknar reit sem er ekki hluti af forminu. Stafurinn o táknar reit sem inniheldur hornið á L-laga kubb. Stafurinn x táknar reit sem inniheldur reit á L-laga kubb sem er ekki horn.
Þú mátt gera ráð fyrir að til sé lausn á gefna inntakinu.
Úttak
Prentið inntakið aftur nema skiptið út stöfunum x fyrir <, ^, >, v þannig að stafurinn bendi að horni kubbsins sem hann tilheyrir.
Ef það eru fleiri en eitt rétt svar verður hvert sem er þeirra samþykkt.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 xo .x x. ox |
4 2 >o .^ v. o< |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 5 xxoxo oxxxx oxxox xxoxo xxoxx oxxox |
6 5 v>o>o o<^v^ o<vo< ^>o>o v>ov^ o<^o< |
| Sample Input 3 | Sample Output 3 |
|---|---|
15 15 ........xx..... .......xoox.... ......xxooxx... .....xoxxxxox.. ....oxxo..oxxx. ...xxox....xoox ..xoxx.....xoox .xxxo.....oxxx. xoox.....xxox.. xoox....xoxx... .xxxo..oxxo.... ..xoxxxxox..... ...xxooxx...... ....xoox....... .....xx........ |
15 15 ........vv..... .......>oo<.... ......v>oo<v... .....>ov^^vo<.. ....o<>o..o<vv. ...v^o<....>oo< ..>ov^.....>oo< .vv>o.....o<^^. >oo<.....v^o<.. >oo<....>ov^... .^^>o..o<>o.... ..>o^vv^o<..... ...^>oo<^...... ....>oo<....... .....^^........ |
