Čtěte prosím tuto stránku celou a pozorně.
Vstupem algoritmu je mřížka v souboru mrizka.txt ve stejném tvaru jako v prvním domácím úkolu. Vstupní mřížka bude obsahovat jen několik děr tak, aby ji bylo možné doplnit na dobrou mřížku, kde žádná dvě políčka nesousedí hranou. Dobrá mřížka je mřížka, která po čtyřech otočeních a přiloženích odkryje každé políčko právě jednou. Program by měl pomocí backtrackingu najít všechna možná dobrá doplnění mřížky bez políček sousedících hranou a zjistit jejich počet.
Předpokládejte, že mřížka je orientovaná (má vršek a spodek). Následující dvě pole reprezentují dvě odlišné mřížky:
10 01 00 00
Během otáčení mřížky každé její políčko postupně vystřídá čtyři různé pozice ve čtyřech různých kvadrantech. Políčka lze tedy sdružit do čtveřic. Dobrá mřížka má v každé čtveřici políček právě jedno políčko s dírou. Všechny mřížky lze vygenerovat tak, že se pro každé políčko z prvního kvadrantu určí jeho čtveřice a ve čtveřici se zvolí jedna díra.
Pro ukládání počtu nalezených mřížek použijte typ Longint.
Vstupy budou vybrány tak, že výpočet nebude trvat déle než jednu sekundu na procesoru s frekvencí 1GHz. Váš program bude považován za chybný v případě, že bude více než 100x pomalejší.
Formát vstupu je stejný jako v prvním domácím úkolu. Velikost mřížky nebude větší než 16.
Výstup by měl být v souboru vystup.txt. Výstupní soubor by měl obsahovat jediný řádek na kterém by měly být pouze arabské číslice 0 až 9. Číslo na řádku odpovídá počtu mřížek a je zapsáno v desítkové soustavě.
Příklady souborů s výstupem najdete v archivu data.tar.gz nebo data.zip.
hruska (zavináč) popelka (tečka) ms (tečka) mff (tečka) cuni (tečka) cz s předmětem zprávy PGM - generator a s přiloženým souborem gen.pas..exe soubory.
Termín zadání: 6.12.2005.
Termín odevzdání: do 18.12.2005 včetně.
Termín odevzdání oprav: do 30.12.2005 včetně.
hruska (zavináč) popelka (tečka) ms (tečka) mff (tečka) cuni (tečka) cz