Sakk

A sakkban a futár az a figura, amelyik csak átlósan tud lépni. Köztudott, hogy a futár csak egyféle színű mezőket ér el, közülük viszont mindegyiket, néhány lépésben (ha feltételezzük, hogy nincs más figura a táblán). Egy sakktábla két adott koordinátája esetén a feladatod annak eldöntése, hogy egy futár el tud-e jutni az első mezőről a másodikra, és ha igen, hogyan. A sakkban a koordinátákat egy betűvel ('A'-tól 'H'-ig) és egy számmal (1-től 8-ig) adjuk meg. A betű határozza meg a tábla egy oszlopát (vonalát), a szám pedig egy sorát.

1. ábra: A sakktábla, a futár és a futár által egy lépésben elérhető mezők.

A bemenet specifikációja

A bemenet a tesztesetek számával kezdődik. Minden teszteset egy sorból áll, amely az X kezdőpozíciót és az Y célpozíciót tartalmazza. A pozíciókat két, szóközzel elválasztott karakter adja meg: egy betű az oszlopot és egy szám a sort. Egy bemeneten nem fog kétszer szerepelni ugyanaz a teszteset.

A kimenet specifikációja

Minden tesztesetre egy sort kell a kimenetre írni. Ha nem lehetséges futárral eljutni X-ből Y-ba, akkor az „Impossible” szót, különben az X-ből Y-ba való eljutás egy lehetséges lépéssorozatát kell kiírni. A lépéssorozatot kezdd n-nel, a lépések számával (amely legfeljebb 4 lehet), majd folytasd n + 1 pozícióval, amelyek a futár útvonalát írják le! A karaktereket egy-egy szóköz válassza el egymástól! Sok lehetséges megoldás létezhet. Közülük mindegyik elfogadható, amelyik legfeljebb 4 lépésből áll. Ne feledd, hogy egy sakklépésben legalább egy figurának (jelen esetben a futárnak) el kell mozdulnia, hogy a lépés érvényes legyen! (Ez azt jelenti, hogy a kimeneten két egymást követő pozíció nem lehet azonos.)

Példa bemenet

1. 3
2. E 2 E 3
3. F 1 E 8
4. A 3 A 3

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. Impossible
2. 2 F 1 B 5 E 8
3. 0 A 3

letöltés szöveges állományként