Speciální domácí úkol - Slon

Čtěte prosím tuto stránku celou a pozorně.

Zadání

Naprogramujte algoritmus, který o konfiguraci skládačky Slon zjistí, zda a na kolik nejméně tahů je možno přejít do jiné konfigurace se zadaným umístěním některých zvířátek.

Skládačku Slon tvoří deset kamenů v dřevěném rámečku (1x slon, 1x krokodýl, 4x žirafa a 4x kachna). Kámen, který má vedle sebe volné místo, je možné posunout. Jeden tah je posunutí kamene o jednu šířku kachny.

Formát vstupu a výstupu

Vstupní soubor vstup.txt obsahuje 11 řádků. Na prvních pěti řádcích je výchozí konfigurace skládačky. Šestý řádek je prázdný. Na posledních pěti řádcích je 'neúplná konfigurace', která se od běžné konfigurace liší tím, že v ní nejsou všechna zvířátka. Váš program by měl najít nejmenší možný počet tahů, které vedou z výchozí konfigurace do neúplné konfigurace. Na umístění kamenů které se v neúplné konfiguraci nevyskytují nezáleží.

V konfiguraci skládačky ve vstupním souboru je na místě slona znak 'S', na místě krokodýla znak 'K', na místě žirafy znak 'Z', na místě kachny znak 'D' a na prázdném políčku je znak '.'.

Příklad vstupního souboru:
ZSSZ
ZSSZ
ZKKZ
Z..Z
DDDD

....
....
....
.SS.
.SS.

Tento vstup požaduje nalezení nejkratší cesty ke konfiguraci, která má slona dole uprostřed. Na rozmístění ostatních kamenů v cílové konfiguraci nezáleží.

Výstupní soubor by měl obsahovat jedno číslo, které odpovídá nejmenšímu možnému počtu tahů do neúplné konfigurace. V případě, že cesta neexistuje, by mělo být ve výstupním souboru číslo -1.

Poznámky

• Formát vstupu a výstupu je povinný, jeho nedodržení je považováno za chybu.
• Program by kromě vstupního textového souboru neměl požadovat žádná data (ani z klávesnice).
• Pro vypracování použijte Delphi, v Borland Pascalu byste nemuseli mít dost paměti.
• Řešení posílejte mailem na adresu hruska (zavináč) popelka (tečka) ms (tečka) mff (tečka) cuni (tečka) cz s předmětem zprávy PGM - slon a s přiloženým programem.
• Po odeslání mailu s domácím úkolem by vám měla přijít zpět zpráva s potvrzením příjmu.
• Neposílejte .exe soubory.
• V případě jakýchkoliv nejasností nebo problémů mi pošlete mail.

Termíny

Termín zadání: 13.8.2007.
Termín odevzdání: do kontroly studijních povinností.