Programozás‎ > ‎Feladatok‎ > ‎

Négyzet alakú csempék

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.

Bemenet

A 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.

Kimenet

Minden 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éretek

Kis bemenet

1 <= T <= 20
1 <= R <= 6
1 <= C <= 6

Nagy bemenet

1 <= T <= 50
1 <= R <= 50
1 <= C <= 50

Példa

Bemenet  Kimenet
3
2 3
###
###
1 1
.
4 5
.##..
.####
.####
.##..
Case #1:
Impossible
Case #2:
.
Case #3:
./\..
.\//\
./\\/
.\/..


Tesztadatok

st_small.in    st_large.in    st_small.out    st_large.out

Címkék

A feladat forrása: Google Code Jam 2011 1C ( online tesztelő )
Algoritmusok: mohó algoritmus

megoldás