5. Domácí úkol - hlavolam

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

Zadání

Naprogramujte program, který zjišťuje nejmenší možný počet tahů, kterými se lze dostat z počáteční do cílové konfigurace hlavolamu.

Konfigurace hlavolamu je zadaná rozmístěním písmen (barev). Příklad: Pětibarevný hlavolam má konfiguraci A B E D C. Každá barva se v konfiguraci vyskytuje právě jednou.

Tah je permutace barev.

Formát vstupu a výstupu

Vstupní data jsou uložena v souboru vstup.txt. Na prvním řádku souboru je počáteční konfigurace hlavolamu. Na druhém řádku souboru je cílová množnina konfigurací, která má stejný formát jako počáteční konfigurace, ale místo některých barev mohou být použity otazníky. Příklad: A B ? ? E.

Na dalších řádcích souboru jsou přípustné tahy. Každý tah je posloupnost čísel, čísla jsou oddělená mezerou a jejich počet je stejný jako počet barev. Příklad: 2 3 1 5 4 odpovídá permutaci 1=>2, 2=>3, 3=>1, 4=>5, 5=>4. Čísla před šipkami tvoří posloupnost 12345, čísla za šipkami je posloupnost načtená ze vstupního souboru.

Ve výstupním souboru by mělo být jen jediné číslo, které odpovídá minimálnímu počtu tahů, kterými se lze dostat z počáteční do cílové konfigurace (může to být i nula).

Můžete počítat s tím, že cílová konfigurace bude vždy dosažitelná. Počet tahů v souboru vstup.txt může být nulový.

Hinty

Použijte algoritmus prohledávání do šířky.

Paměťové nároky

Počet barev nebude vyšší než 20. Počet vrcholů, které navštíví algoritmus prohledávání do šířky nebude větší než 1000. Počet tahů nebude větší než 100.

Ukázková data

Příklady souborů s výstupem najdete v archivu data.tar.gz nebo data.zip.

Poznámky

• Formát vstupu a výstupu je povinný, jeho nedodržení je považováno za chybu.
• Program kromě vstupního textového souboru nesmí požadovat žádná data (ani z klávesnice).
• Do programu prosím vložte komentář se svým jménem a příjmením.
• Ř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 - hlavolam a s přiloženým souborem hlavolam.pas.
• 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í: 20.12.2005.
Termín odevzdání: do 8.1.2006 včetně.
Termín odevzdání oprav: libovolný