Informatyka I rok
Laboratorium Metod Programowania
2001/2002

Zadanie z dnia: 11.03.02
Termin odbioru: 25.03.02

Zad. 1  

Należy napisać program Ariadna. Program ma umożliwić wyszukanie drogi 
w labiryncie między dwoma zadanymi punktami. Labirynt jest reprezentowany
przez tablicę typu:
   array[0..Max_n+1, 0..Max_k+1] of integer;
Wartości 0 oznaczają ściany, wartości 1 oznaczają wolne pola. Aby nie zagubić
się w labiryncie należy posłużyć się nicią Ariadny. Rolę nici ma pełnić lista
prosta, kolejne elementy listy mają odpowiadać kolejnym polom odwiedzanym
w labiryncie. Należy samemu ustalić jakie informacje o polu warto przechowywać
w elemencie listy i gdzie powinien być początek tej listy. W elementach tablicy 
można wpisywać informacje o tym, czy poszczególne pola były już odwiedzone.

Uwaga:
  Podany powyżej sposób rozwiązania zadania jest jednym z wielu możliwych 
  (inne to np. rekurencja, bądź pamiętanie w polach labiryntu informacji 
  o kierunku, z którego wędrowiec wszedł na dane pole). W tym zadaniu
  _wymagamy_ rozwiązania w opisany w treści sposób. 

Labirynt należy wczytać z pliku tekstowego. Format pliku jest nastepujący:
 - pierwszy wiersz zawiera dwie liczby n i k, określające rozmiary labiryntu,
 - kolejne n wierszy ma długość k, każdy znak opisuje jedno pole (X oznacza
   ścianę, podkreślenie oznacza puste pole).
Należy przyjąć w programie stosowne ograniczenie na dozwolone wielkości
liczb k i n. Program ma sprawdzać poprawność danych. W przypadku 
niepoprawnych danych należy wypisać komunikat o błędzie i przerwać 
działanie programu. Nie wymagamy, by w pliku labirynt był otoczony murem,
program powinien pamiętać labirynt w tablicy Max_n+2 na Max_k+2 i samodzielnie 
wypełnić brzegi labiryntu ścianami.

Napisz program Ariadna, który należy wywoływać w następujący sposób:
   Ariadna plik_z_labiryntem 
Program ma:
  - wyrysować na ekranie labirynt, wypisać jego rozmiary, ewentualnie dodatkowe
     dane ułatwiające lokalizację pól labiryntu (np. współrzędne mod 10),
  - wczytywać od użytkownika dwie pary liczb (współrzędne początku i końca drogi),
  - jeśli dane są poprawne (pola w labiryncie i nie będące ścianami), to program powinien
    rozpocząć wyszukiwanie drogi. W trakcie wyszukiwania na ekranie należy wypisywać:
      - długość nici Ariadny,
      - wielkość zajętej pamięci (MemAvail i MaxAvail),
      - aktualne położenie wędrowca w labiryncie,
      - zaznaczać na rysunku labiryntu kolorami  pola odwiedzone i pole bieżące.
  - wypisać informację, czy udało się znaleźć drogę.

Program powinien być tak napisany, by łatwo można bylo przeprowadzić eksperyment,
polegający na tym, że przy wycofywaniu się z pola labiryntu stan tego pola zmienia się
z powrotem na nieodwiedzone (jak wpłynie to na efektywność rozwiązania?). Oczywiście
program ma zamykać plik i ma zwalniać pamięć.

Pomocne uwagi o BP:
 - czyszczenie ekranu: ClrScr,
 - ustawienie kursora we wskazanym miejscu ekranu: GotoXY(x,y). Operacja write
   wykonana po wywołaniu GotoXY będzie wypisywać w zadanym miejscu ekranu,
 - zmiana koloru pisanego tekstu: TextColor(Nr_koloru), Nr_koloru to liczba z zakresu
   0..15,
 - zmiana koloru tła pisanego tekstu: TextBackground(Nr_koloru), Nr_koloru j.w.,
 - wstrzymanie wykonywania programu: Delay(czas), czas jest wyrażony w milisekundach,
Wszystkie powyższe operacje pochodzą z modułu CRT, żeby móc z niego skorzystać
należy na początku programu napisać:
    Uses CRT;

Zwróć uwagę na nasze wymagania dotyczące zapisu programu (wcięcia, komentarze), za
niestosowanie się do nich też raci się punkty.

Miejsce skąd można pobierać treści zadań zaliczeniowych: 
   www.mimuw.edu.pl/~janusz (i potem dość oczywiste dowiązania)