Gyönyörű geometriai mintázatokat árulsz, amelyek 1x1-es négyzet alakú csempékből állnak. A csempék nem fedik át egymást.Például:
.##.. .#### .#### .##.. A kék csempéket '#' karakter, a fehéreket '.' karakter jelöli. Más színeket nem használsz. Mivel nem mindenki szereti a kéket, néhány vevőd szeretné pirosra cserélni a minta kék részeit. Sajnos a piros csempék csak 2x2-es méretben kaphatók, és nem lehet feldarabolni őket. Egy kék csempékből álló 2x2-es rész helyettesíthető egyetlen piros csempével, és ez addig ismételhető, amíg van ilyen 2x2-es rész. De arra vigyázni kell, hogy a piros csempék sem fedhetik egymást, és nem lóghatnak ki az eredeti képből. Például a fenti minta így alakítható át: ./\.. .\//\ ./\\/ .\/.. Minden piros csempe két '/' karakterből (bal-felső, jobb-alsó) és két '\' karakterből áll össze. FeladatÍrjunk programot, ami eldönti, hogy a kék-fehér minta átalakítható-e a piros-fehér mintába.
BemenetA bemenet első sora a tesztesetek T számát adja meg, utána pedig minden teszteset első sora a minta sorainak R és oszlopainak C számát. Ezután pedig a minta következik, a fent leírt kódolás szerint.
KimenetMinden tesztesethez írjuk ki a piros-fehér minta megfelelő kódolását, vagy az 'Impossible' szöveget, ha az átalakítás nem végezhető el.
MéretekKis bemenet1 <= T <= 20 1 <= R <= 6 1 <= C <= 6 Nagy bemenet1 <= T <= 50 1 <= R <= 50 1 <= C <= 50 Példa
Tesztadatokst_small.in st_large.in st_small.out st_large.out CímkékA feladat forrása: Google Code Jam 2011 1C ( online tesztelő )
Algoritmusok: mohó algoritmus
megoldás |
Programozás > Feladatok >