Problem D
Press


Källkod: press.pas, press.p, press.c eller press.cc

I det italienska barnspelet Pressen skall man förskjuta ett antal block i sidled och därefter pressa samman spelplanen så mycket det går. Lyckas man pressa ihop spelplanen så att den består av endast en "rad" har man lyckats besegra spelet. Spelet har en väldigt vacker design i sin kommersiella variant, men för att underlätta beskrivningen av spelet kan man beskriva den rektangulära spelplanen med att den består av ett antal rader, där det finns exakt ett block per rad. Varje block består i sin tur av ett antal kvadratiska segment av fix storlek, där vissa är ihoppressbara (på höjden, men ej på bredden) medan de andra inte är det. Spelet går ut på att skjuta varje block i sidled på sin rad och därefter pressa ihop spelplanen. Består spelplanen nu bara av en rad har man lyckats "lösa" spelet.

Nedanstående exempelspel visar ett press-spel med 4 block.


Uppgiften är alltså att skriva ett program som avgör om det går att pressa ihop ett givet antal block i "pressen", eller ej.

Indata:

Första raden anger antalet testfall programmet skall behandla (N). Därefter följer de N testfallen. Första raden i varje testfall anger pressens storlek genom antalet block (M< 5) samt pressens bredd (B < 15). Följande M rader beskriver blockens utseende, med ett block per rad. Varje blockrad innehåller ett antal s och p (solid resp. pressable) som beskriver blockets olika segment. Ett block innehåller alltid minst ett icke ihoppressbart segment, och totalt högst B segment.

Utdata:

Skall bestå av N rader, en för varje testfall med texten 'Possible'om det är möjligt att placera blocken så att de går att pressa ihop till en rad, eller texten 'Impossible', om det inte går.

Exempel:

Indata:

2
4 8
s
spss
ppsps
sps
4 8
s
spss
sspps
sps

Utdata:

Possible
Impossible