Čtěte prosím tuto stránku celou a pozorně.
Sokolovská ulice v Karlíně byla po povodni v roce 2002 obtížně průchodná. Na ulici překážely nejrůznější věci, které přinesla voda. Vaším úkolem je naprogramovat program, který rozhodne, zda je ulice průchozi z jednoho konce na druhý, či nikoliv.
Vstupem algoritmu je dvourozměrné pole znaků, které má relativně malou šířku (maximálně několik desítek prvků), ale zato je velmi dlouhé (jako ulice). Prvky pole reprezentují mapu ulice. Obsahují dva druhy hodnot:
'1''0'Mezi dvěma průchozími políčky je možno projít jen sousedí-li spolu hranou. Úhlopříčně procházet nelze. Na obrázku jsou příklady dvou ulic. První z nich je průchozí, druhá ne. Překážky jsou vyznačeny černě, zbytek je průchozí. Zeleně jsou vyznačeny dostupné oblasti.
Vstup je realizován pomocí unity ulice.pas. Na začátek vlastního programu v souboru karlin.pas je potřeba vložit řádek uses ulice;, aby bylo možné volat procedury a funkce implementované v souboru ulice.pas. Nejprve je potřeba volat proceduru ulice_init, potom už je možné volat funkci next, která vrací jeden řádek mapy ulice ve formě řetězce. Na konci programu je potřeba zavolat proceduru ulice_done.
klauzule uses ulice; zpřístupní také konstantu sirka (šířka ulice) a datový typ t_rada.
Jedna z implementací unity ulice vygeneruje náhodnou mapu. Parametry takto vygenerované ulice je možné měnit změnou hodnot konstant přímu v unitě. Konstanta delka určuje délku ulice, konstanta hustota určuje poměr políček s překážkou vůči volně průchozím políčkům. Smysluplné hodnoty hustoty jsou od 1 do 1000. Konstanta initial_seed se používá k inicializaci náhodného generátoru čísel. Změnou její hodnoty obdržíte jinou (náhodnou) mapu se stejnou hustotou a délkou.
Váš program může být testován s jinou implementací unity ulice, která načítá testovací data ze souboru. Proto je potřeba vždy volat procedury ulice_init (otevření souboru) a ulice_done (zavření souboru).
Výstup by měl být zapsán do výstupního souboru vystup.txt v aktuálním adresáři. Je-li ulice průchozí, měl by soubor obsahovat písmeno 'A', není-li ulice průchozí, měl by obsahovat písmeno 'N'.
Zde je program file.pas, který vytvoří soubor vystup.txt a zapíše do něj jedno písmeno.
Ukázkový soubor karlin.pas a dvě z možné implementace ulice.pas jsou v souboru karlin.tar.
Soubory ve formátu .tar lze rozbalit například Total Commanderem, nebo pomocí programu tar.exe příkazem "C:\>tar.exe xvf karlin.tar". Více informací o použití programu tar najdete zde.
Průchod ulice lze naprogramovat s množstvím paměti, které je úměrné šířce ulice. Použijete-li algoritmus, který potřebuje tolik paměti, jak dlouhá je ulice, pravděpodobně vám paměť stačit nebude.
Jeden z možných algoritmů dokáže průchodnost ulice zjistit během jednoho načtení dat. Algoritmus pracuje tak, že postupně načítá řady mapy (pomocí funkce next a udržuje si přehled o tom, která políčka v řadě jsou navzájem průchozí skrz již načtený úsek ulice. Při načtení další řady algoritmus upraví průchodnost (dvě navzájem průchozí oblasti se mohly spojit, nějaká mohla zaniknout, nebo naopak nějaká vzniknout). Jedním ze způsobů, jak udržovat přehled o navzájem přístupných políčkách, je obarvit vzájemně přístupná políčka stejnou barvou (v praxi spíš číslem barvy). Ulice je pak průchozí právě když se jedna z barev, která byla přítomna v první řadě na začátku ulice udrží během průchodu až na konec (předpoklad je, že v případě spojení dvou oblastí se pro obarvení spojené oblasti použila barva z první řady mapy).
Příklad barvení oblastí je na následujícím obrázku.
Příklady souborů s výstupem najdete v archivu karlin.tar.
hruska (zavináč) popelka (tečka) ms (tečka) mff (tečka) cuni (tečka) cz s předmětem zprávy PGM - karlin a s přiloženým souborem karlin.pas..exe soubory.
Termín zadání: 27.10.2006.
Termín odevzdání: do 12.11.2006 včetně.
Termín odevzdání oprav: do 19.11.2006 včetně.
hruska (zavináč) popelka (tečka) ms (tečka) mff (tečka) cuni (tečka) cz