Programozás‎ > ‎Feladatok‎ > ‎

Aknakereső

Az Aknakereső egy ismert játék a 80-as évekből. A Microsoft Windows bizonyos verzióiban a mai napig előre telepítve van. 

A játék egy cellákból álló négyzetrácson zajlik. A cellák tartalma eredetileg el van rejtve. Összesen  M cellában akna található (egy cellában legfeljebb egy akna lehet). A cellákra rákattinthatunk, hogy megismerjük tartalmukat. Ha olyan cellára kattintunk, amiben aknak van, vége a játéknak. Egyébként egy szám jelenik meg a cellában, ami 0 és 8 közé esik, és azt adja meg, hogy a választott cella nyolc szomszédjában összesen hány akna van. A szomszédság egy közös él vagy egy közös csúcs kell. 

Ha a felfedett cella 0 szomszédja tartalmaz aknát, akkor összes szomszédja is felfedetté válik, és ez rekurzív folytatódik a szomszédok szomszédaival.

Ha az összes cella fel lett fedve, ami nem tartalmaz aknát, megnyertük a játékot.

A következő példában egy játék kezdeti állapotát láthatjuk ('*' jelöli az aknát, 'c' az első kattintás helyét, '.' pedig az üres cellát):

*..*...**.
....*.....
..c..*....
........*.
..........
Mivel az eredeti kattintás szomszédságában nincs akna, ő nulára lesz állítva, és a nyolc szomszédja is fel lesz fedve. A folyamat egészen addig folytatódik, amíg az alábbi állapothoz nem jutunk:
*..*...**.
1112*.....
00012*....
00001111*.
00000001..
Mivel még vannak fel nem fedett cellák, újra kattintani kell a játék folytatásához. 

Feladat

Szeretnénk a játékot gyorsan megnyerni, ezért szeretnénk tudni, hogy egy (R x C) méretű táblán el lehet-e helyezni úgy  M aknát, hogy a tábla egyetlen kattintással megnyerhető legyen. Az első kattintás helyét megválaszthatjuk.  Ha lehetséges, akkor írjunk ki egy megfelelő akna-konfigurációt, megjelölve az első kattintás helyét. Ha nem lehetséges, akkor az "Impossible" szöveget kell kiírni.


Bemenet

Az első sor a tesztesetek, T számát adja meg. Ezután T sorban három-három egész következik: RC, és M.

Kimenet

Minden tesztesethez ki kell rajzolni egy megfelelő akna-konfigurációt, R sorban, soronként C karakterrel. A kezdeti (nyerő) kattintást 'c' jelöli. 

Ha nincs jó konfiguráció, akkor az "Impossible" szöveget kell kiírni. Ha több jó konfiguráció van, akkor bármelyik megadható.

Méretek

0 ≤ M < R * C.

Kis bemenet

1 ≤ T ≤ 230.
1 ≤ RC ≤ 5.

Nagy bemenet

1 ≤ T ≤ 140.
1 ≤ RC ≤ 50.

Példa


Input 
 

Output 
 
5
5 5 23
3 1 1
2 2 1
4 7 3
10 10 82

Case #1:
Impossible
Case #2:
c
.
*
Case #3:
Impossible
Case #4:
......*
.c....*
.......
..*....
Case #5:
**********
**********
**********
****....**
***.....**
***.c...**
***....***
**********
**********
**********

Tesztadatok

Címkék

A feladat forrása: Google Code Jam 2014 Qualification Round, Minesweeper Master
Algoritmusok: