Znajdowanie drogi w labiryncie


Tematy pokrewne
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie

Labirynt jako graf

Użyteczność teorii grafów jest tak duża, ponieważ grafy potrafią odwzorowywać wiele skomplikowanych obiektów ze świata rzeczywistego. Typowym przykładem jest labirynt, który często pojawia się w zadaniach olimpiady informatycznej. W tym rozdziale pokażemy zastosowanie opisanego wcześniej algorytmu wyszukiwania ścieżki w grafie do znalezienia wyjścia z labiryntu.

Labirynt będziemy reprezentować w postaci dwuwymiarowej tablicy znaków ASCII o rozmiarze m wierszy na n kolumn. Dane do programu można przygotować sobie w notatniku Windows. Tablica będzie zawierała następujące znaki:

 

# - ściana
. - korytarz
S - start
W - wyjście
* - koniec danych

 

W ostatnim wierszu umieszczamy znak końca danych *. Wokół labiryntu musi być "ściana" (inaczej program wyjdzie "poza" labirynt i nastąpi błąd). Na przykład:

 

########################################
#S.##..#.....###.................##....#
##.#.....#.#...#.######.###..###.#..####
#..#.###.#.#.###.#....###.##.#.........#
##...#.###.#.#...#.#.##......###########
####.....###.#.###.#.#..#..#..#........#
#.....##.#...#.....#.##.#.############.#
#####..###.#########.#..#.#............#
#........#.#.........##.#.##.###.#####.#
#.###.##.#.#.#######..#.#..#.#.#.....#.#
#...#..#.#.#.#........#.####.#.#####.#.#
###.####.#.#.###.#.#..#......#.......#.#
#...#....#.#.....#######.#####.#####.#.#
###.#.#.##.#####.#.....#.......#.....#.#
#...###....###.#.#.#.#.###############.#
#.#...########.#.#.#.#.................#
###.#.#........#.#.#########.###########
#...#....#####.#.#...#.....#.......#...#
#.########...###.#.#.#.#####.#.###.#.###
#..........#.....#.#.........#...#....W#
########################################
*

Pozostaje problem interpretacji tych danych jako grafu. Rozwiązanie jest bardzo proste. Każdy znak tablicy będzie odpowiadał "wierzchołkowi" grafu. Znak "#" to wierzchołek izolowany, do którego nie prowadzą żadne krawędzie. Pozostałe znaki oznaczają wierzchołki połączone krawędziami.

 

 

Krawędzie istnieją jedynie pomiędzy sąsiadującymi ze sobą wierzchołkami. Wierzchołki sąsiadują ze sobą jedynie w poziomie i w pionie (a nie np. po przekątnej). Informacja o istnieniu krawędzi jest zawarta wewnątrz samej tablicy znakowej. Do sąsiedniego wierzchołka możemy przejść, jeśli zawiera on znak korytarza ".". Jeśli jest to inny znak, to przejście nie jest możliwe (nie istnieje krawędź łącząca te dwa wierzchołki).

Do wyszukania ścieżki zastosujemy algorytm opisany w poprzednim rozdziale. Wykorzystamy przejście BFS, które gwarantuje znalezienie najkrótszej ścieżki. Zasada pracy naszego algorytmu jest następująca:

 

Po odczytaniu tablicy poszukamy w niej położenia znaków S i W. Położenie to zapamiętamy w odpowiednich zmiennych. Znak S pozostawimy bez zmian, natomiast znak W zastąpimy znakiem korytarza ".", aby algorytm mógł dojść do tego miejsca.

Następnie uruchomimy algorytm szukania ścieżki przejściem BFS – w tej wersji kolejka będzie przechowywała współrzędne kolejno odwiedzanych wierzchołków, tzn. numery wiersza i kolumny, w których znajduje się przetwarzany wierzchołek/znak labiryntu. Na początku w kolejce umieścimy współrzędne znaku S, które znaleźliśmy w początkowej fazie algorytmu. Wyszukiwanie trwa dotąd, aż algorytm dojdzie do współrzędnych znaku W lub wyczerpie wszystkie dostępne wierzchołki. W tym drugim przypadku ścieżka nie istnieje i należy wypisać odpowiednią informację.

W trakcie przeglądania labiryntu algorytm umieszcza w komórkach tablicy informację o tym, skąd do danej komórki przyszedł. Informacja ta składa się z jednej z czterech małych liter:

 

g - z góry,  tzn. ze znaku leżącego w wierszu powyżej
d - z dołu,  tzn. ze znaku leżącego w wierszu poniżej
l - z lewa,  tzn. ze znaku leżącego po lewej stronie
p - z prawa, tzn. ze znaku leżącego po prawej stronie


Informacja ta posłuży na końcu do wyznaczenia przebytej ścieżki. Drugą funkcją tych znaków jest zastąpienie tablicy visited. Przetworzenie węzła polega na  sprawdzeniu, czy nie jest to węzeł, który pierwotnie zawierał literkę W. Jeśli tak, to wyszukiwanie jest przerywane. W przeciwnym razie algorytm sprawdza czterech sąsiadów (górnego, dolnego, lewego i prawego). Sąsiad nieodwiedzony jest znakiem korytarza "." i jego współrzędne trafiają do kolejki po wstawieniu znaku kierunku przyjścia (g,d,p,l).

Gdy wyszukiwanie ścieżki się zakończy, to sprawdzana jest zawartość lokacji w tablicy, która początkowo zawierała znak W (znak ten został zastąpiony przez znak korytarza "."). Jeśli w tym miejscu mamy wciąż znak korytarza ".", to algorytm BFS nie odnalazł ścieżki, W przeciwnym razie idziemy wstecz po znakach g,d,p,l aż do pozycji S. Każdy ze znaków zamieniamy na znak "+".

Na koniec usuwamy z tablicy pozostałe znaki kierunków, odtwarzamy znak W na jego oryginalnej pozycji i wyświetlamy treść tablicy.

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program wczytuje definicję labiryntu w postaci ciągu wierszy znaków. W ostatnim wierszu musi się znaleźć znak *. Do przechowywania labiryntu program wykorzystuje dynamiczną tablicę łańcuchów znakowych. Wielkość tej tablicy jest na bieżąco dopasowywana do napływających danych. Zasada takiego dopasowania jest opisana w rozdziale o macierzach.

 

Lazarus
// Znajdowanie wyjścia z labiryntu
// Data: 25.08.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------

program labirynt;

// Typy dla kolejki
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      head : PslistEl;
      tail : PslistEl;

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      procedure push(v : integer);
      procedure pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if head = nil then empty := true
  else               empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then front := -MAXINT
  else               front := head^.v;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push(v : integer);
var
  p : PslistEl;
begin
  new(p);
  p^.next := nil;
  p^.v := v;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose(p);
  end;
end;

// Zmienne globalne
//-----------------

var
  ws,ks : integer;      // Współrzędne startowe - wiersz, kolumna
  ww,kw : integer;      // Współrzędne wyjścia  - wiersz, kolumna
  L : array of string;  // Labirynt

// Odczytuje labirynt
// Wyszukuje wierzchołki
// startowy i wyjściowy
//----------------------
procedure czytajL;
var
  s : string;
  i,j : integer;
begin
  i := 0;                 // Licznik wierszy
  repeat
    readln(s);            // Czytamy wiersz z wejścia
    if s <> '*' then      // Jeśli nie jest to wiersz końcowy, to
    begin
      if Length(L) < i+1 then SetLength(L,i+10); // ustawiamy rozmiar tablicy
      L[i] := s;          // odczytany wiersz umieszczamy w tablicy M
      inc(i);             // zwiększamy licznik wierszy
    end;
  until s = '*';

  ws := -1; ks := -1;     // Ustawiamy wstępnie współrzędne startu
  ww := -1; kw := -1;     // oraz wyjścia

  for i := 0 to High(L) do // Szukamy S i W
    for j := 1 to Length(L[i]) do
      if L[i][j] = 'S' then
      begin
        ws := i; ks := j; // S znalezione
      end
      else if L[i][j] = 'W' then
      begin
        ww := i; kw := j; // W znalezione
        L[i][j] := '.';
      end;
end;

// Procedura szukania wyjścia
//---------------------------
procedure SzukajW;
var
  Q   : queue;
  w,k : integer;             // Wiersz, kolumna bieżącego wierzchołka
  i,j : integer;

begin
  Q.init;                    // Inicjujemy kolejkę

  Q.push(ws);                // W kolejce umieszczamy wierzchołek startowy
  Q.push(ks);

  while Q.empty = false do
  begin
    w := Q.front; Q.pop;     // Pobieramy z kolejki wiersz
    k := Q.front; Q.pop;     // i kolumnę bieżącego wierzchołka

    // Sprawdzamy, czy osiągnęliśmy wyjście

    if (w = ww) and (k = kw) then break;

    // Przeglądamy sąsiadów bieżącego wierzchołka

    for i := -1 to 1 do
      for j := -1 to 1 do
        if (i <> j) and ((i = 0) or (j = 0)) then
        begin
          if L[w+i][k+j] = '.' then
          begin

            // W komórce sąsiada zapisujemy, skąd przyszliśmy do niej

            if      i = -1 then L[w+i][k+j] := 'd'   // z dołu
            else if i =  1 then L[w+i][k+j] := 'g'   // z góry
            else if j = -1 then L[w+i][k+j] := 'p'   // z prawej
            else                L[w+i][k+j] := 'l';  // z lewej

            Q.push(w+i);       // Sąsiad zostaje umieszczony w kolejce
            Q.push(k+j);
          end;
        end;
  end;
  Q.destroy;              // Czyścimy kolejkę
end;

// Procedura wypisuje labirynt z ewentualną ścieżką
// Zastępuje znaki kierunków znakiem +.
//-------------------------------------------------
procedure PiszL;
var
  i,j : integer;
  c   : char;
begin

  // Najpierw sprawdzamy, czy ścieżka została znaleziona
  // Jeśli tak, to zastępujemy ją znakami +

  if L[ww][kw] <> '.' then
  begin
    i := ww; j := kw;
    while (i <> ws) or (j <> ks) do
    begin
      c := L[i][j];
      L[i][j] := '+';
      case c of
        'd' : inc(i);
        'g' : dec(i);
        'p' : inc(j);
        'l' : dec(j);
      end;
    end;
  end;

  L[ww][kw] := 'W'; // Odtwarzamy znak wyjścia

  // Teraz usuwamy znaki kierunku i wypisujemy labirynt

  for i := 0 to High(L) do
  begin
    for j := 1 to Length(L[i]) do
      case L[i][j] of
        'g','d','p','l' : L[i][j] := ' ';
      end;
    writeln(L[i]);
  end;
  writeln;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

begin
  czytajL;    // Wczytujemy labirynt
  if (ws = -1) or (ks = -1) or (ww = -1) or (kw = -1) then
    writeln('BRAK DEFINICJI S LUB W !!!')
  else
  begin
    SzukajW; // Szukamy wyjścia
    PiszL;   // Wyświetlamy wyniki poszukiwań
  end;
end.
Code::Blocks
// Znajdowanie wyjścia z labiryntu
// Data: 25.08.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------

#include <iostream>
#include <string>

using namespace std;

const int MAXINT = -2147483647;

// Typy dla kolejki

struct slistEl
{
  slistEl * next;
  int v;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * tail;

  public:
    queue();      // konstruktor
    ~queue();     // destruktor
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue()
{
  head = tail = NULL;
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue()
{
  while(head) pop();
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty(void)
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front(void)
{
  if(head) return head->v;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push(int v)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->v = v;
  if(tail) tail->next = p;
  else     head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop(void)
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
}

// Zmienne globalne
//-----------------

int wst,kst;                  // Współrzędne startowe - wiersz, kolumna
int wwy,kwy;                  // Współrzędne wyjścia  - wiersz, kolumna
int n = 10;                   // Liczba wierszy
string * L = new string [n];  // Labirynt

// Odczytuje labirynt
// Wyszukuje wierzchołki
// startowy i wyjściowy
//----------------------
void czytajL()
{
  string s, * T;
  int i,j;

  i = 0;                  // Licznik wierszy
  do
  {
    cin >> s;             // Czytamy wiersz z wejścia
    if(s != "*")          // Jeśli nie jest to wiersz końcowy, to
    {
      if(n < i+1)         // ustawiamy rozmiar tablicy
      {
        T = new string [i + 10];
        for(j = 0; j < n; j++) T[j] = L[j];
        delete [] L;
        L = T;
        n = i + 10;
      }
      L[i++] = s;         // odczytany wiersz umieszczamy w tablicy M
    }
  } while(s != "*");

  n = i;                  // Liczba wierszy w L

  wst = kst = wwy = kwy = -1; // Współrzędne startu oraz wyjścia

  for(i = 0; i < n; i++)  // Szukamy S i W
    for(j = 0; j < (int)L[i].length(); j++)
      if(L[i][j] == 'S')
      {
        wst = i; kst = j;   // S znalezione
      }
      else if(L[i][j] == 'W')
      {
        wwy = i; kwy = j;   // W znalezione
        L[i][j] = '.';
      }
}

// Procedura szukania wyjścia
//---------------------------
void SzukajW()
{
  queue Q;
  int w,k;                   // Wiersz, kolumna bieżącego wierzchołka
  int i,j;

  Q.push(wst);               // W kolejce umieszczamy wierzchołek startowy
  Q.push(kst);

  while(!Q.empty())
  {
    w = Q.front(); Q.pop();  // Pobieramy z kolejki wiersz
    k = Q.front(); Q.pop();  // i kolumnę bieżącego wierzchołka

    // Sprawdzamy, czy osiągnęliśmy wyjście

    if((w == wwy) && (k == kwy)) break;

    // Przeglądamy sąsiadów bieżącego wierzchołka

    for(i = -1; i <= 1; i++)
      for(j = -1; j <= 1; j++)
        if((i != j) && (!i || !j))
        {
          if(L[w+i][k+j] == '.')
          {
            // W komórce sąsiada zapisujemy, skąd przyszliśmy do niej

            if(     i == -1) L[w+i][k+j] = 'd';  // z dołu
            else if(i ==  1) L[w+i][k+j] = 'g';  // z góry
            else if(j == -1) L[w+i][k+j] = 'p';  // z prawej
            else             L[w+i][k+j] = 'l';  // z lewej

            Q.push(w+i);       // Sąsiad zostaje umieszczony w kolejce
            Q.push(k+j);
          }
        }
  }
}

// Procedura wypisuje labirynt z ewentualną ścieżką
// Zastępuje znaki kierunków znakiem -.
//-------------------------------------------------
void PiszL()
{
  int i,j;
  char c;

  // Najpierw sprawdzamy, czy ścieżka została znaleziona
  // Jeśli tak, to zastępujemy ją znakami +

  if(L[wwy][kwy] != '.')
  {
    i = wwy; j = kwy;

    while((i != wst) || (j != kst))
    {
      c = L[i][j];
      L[i][j] = '+';
      switch(c)
      {
        case 'd' : i++; break;
        case 'g' : i--; break;
        case 'p' : j++; break;
        case 'l' : j--; break;
      }
    }
  }

  L[wwy][kwy] = 'W'; // Odtwarzamy znak wyjścia

  // Teraz usuwamy znaki kierunku i wypisujemy labirynt

  for(i = 0; i < n; i++)
  {
    for(j = 0; j < (int)L[i].length(); j++)
      switch(L[i][j])
      {
        case 'g': ;
        case 'd': ;
        case 'p': ;
        case 'l': L[i][j] = ' ';
      }
    cout << L[i] << endl;
  }
  cout << endl;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  czytajL();    // Wczytujemy labirynt

  if((wst == -1) || (kst == -1) || (wwy == -1) || (kwy == -1))
    cout << "BRAK DEFINICJI S LUB W !!!\n";
  else
  {
    SzukajW(); // Szukamy wyjścia
    PiszL();   // Wyświetlamy wyniki poszukiwań
  }
  return 0;
}
Free Basic
' Znajdowanie wyjścia z labiryntu
' Data: 25.08.2013
' (C)2013 mgr Jerzy Wałaszek
'--------------------------------

Const MAXINT = 2147483647

' Typy dla kolejki

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As slistEl Ptr
    tail As slistEl Ptr

  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue()
  head = 0
  tail = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue()
  While empty = 0: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty() As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front() As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->v
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal v As Integer)
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->v = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  Dim p As slistEl Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

' Zmienne globalne
'-----------------

Dim Shared As Integer wst,kst ' Współrzędne startowe - wiersz, kolumna
Dim Shared As Integer wwy,kwy ' Współrzędne wyjścia  - wiersz, kolumna
Dim Shared As Integer n = 10  ' Liczba wierszy
Dim Shared As String L(n)     ' Labirynt

' Odczytuje labirynt
' Wyszukuje wierzchołki
' startowy i wyjściowy
'----------------------
Sub czytajL()

  Dim As String s
  Dim As Integer i,j

  Open Cons For Input As #1
   
  i = 0                   ' Licznik wierszy
  Do
    Line Input #1;s       ' Czytamy wiersz z wejścia
    If s <> "*" Then      ' Jeśli nie jest to wiersz końcowy, to
      If n < i Then       ' ustawiamy rozmiar tablicy
        ReDim Preserve L(i + 10)
        n = i + 10
      End If
      L(i) = s            ' odczytany wiersz umieszczamy w tablicy M
      i += 1
    End If
  Loop Until s = "*"

  Close #1
  
  n = i                   ' Liczba wierszy w L

  wst = - 1: kst = -1: wwy = -1: kwy = -1 ' Współrzędne startu oraz wyjścia

  For i = 0 To n-1        ' Szukamy S i W
    For j = 1 To Len(L(i))
    	If Mid(L(i),j,1) = "S" Then 
        wst = i: kst = j  ' S znalezione
    	ElseIf Mid(L(i),j,1) = "W" Then
        wwy = i: kwy = j  ' W znalezione
        Mid(L(i),j,1) = "."
      End If
    Next
  Next
End Sub

' Procedura szukania wyjścia
'---------------------------
Sub SzukajW()
  Dim As queue Q
  Dim As Integer w,k         ' Wiersz, kolumna bieżącego wierzchołka
  Dim As Integer i,j

  Q.push(wst)                ' W kolejce umieszczamy wierzchołek startowy
  Q.push(kst)

  While Q.empty() = 0
  	
    w = Q.front(): Q.pop()   ' Pobieramy z kolejki wiersz
    k = Q.front(): Q.pop()   ' i kolumnę bieżącego wierzchołka

    ' Sprawdzamy, czy osiągnęliśmy wyjście

    If (w = wwy) AndAlso (k = kwy) Then Exit while

    ' Przeglądamy sąsiadów bieżącego wierzchołka

    For i = -1 To  1
      For j = -1 To 1
        If (i <> j) AndAlso ((i = 0) OrElse (j = 0)) Then
          If Mid(L(w+i),k+j,1) = "." Then

            ' W komórce sąsiada zapisujemy, skąd przyszliśmy do niej

            If i = -1 Then
              Mid(L(w+i),k+j,1) = "d"  ' z dołu
            ElseIf i =  1 Then
              Mid(L(w+i),k+j,1) = "g"  ' z góry
            ElseIf j = -1 Then
              Mid(L(w+i),k+j,1) = "p"  ' z prawej
            Else
              Mid(L(w+i),k+j,1) = "l"  ' z lewej
            End If

            Q.push(w+i)       ' Sąsiad zostaje umieszczony w kolejce
            Q.push(k+j)
          End if
        End If
      Next
    Next
  Wend
End Sub

' Procedura wypisuje labirynt z ewentualną ścieżką
' Zastępuje znaki kierunków znakiem -.
'-------------------------------------------------
Sub PiszL()

  Dim As Integer i,j
  Dim As String * 1 c

  ' Najpierw sprawdzamy, czy ścieżka została znaleziona
  ' Jeśli tak, to zastępujemy ją znakami +

  if Mid(L(wwy),kwy,1) <> "." Then

    i = wwy: j = kwy

    While (i <> wst) OrElse (j <> kst)
      c = Mid(L(i),j,1)
      Mid(L(i),j,1) = "+"
      Select Case c
      	Case "d"
          i += 1
      	Case "g"
          i -= 1
      	Case "p"
          j += 1
      	Case "l"
          j -= 1
      End Select
    Wend
  End If

  Mid(L(wwy),kwy,1) = "W" ' Odtwarzamy znak wyjścia

  ' Teraz usuwamy znaki kierunku i wypisujemy labirynt

  For i = 0 To n - 1
    For j = 0 To Len(L(i))
      Select Case Mid(L(i),j,1)
        Case "g","d","p","l"
          Mid(L(i),j,1) = " "
      End Select
    Next
    Print L(i)
  Next
  Print
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

czytajL()    ' Wczytujemy labirynt
Print
If (wst = -1) OrElse (kst = -1) OrElse (wwy = -1) OrElse (kwy = -1) Then
  Print "BRAK DEFINICJI S LUB W !!!"
Else
  SzukajW()  ' Szukamy wyjścia
  PiszL()    ' Wyświetlamy wyniki poszukiwań
End If

End
Wynik
########################################
#S.##..#.....###.................##....#
##.#.....#.#...#.######.###..###.#..####
#..#.###.#.#.###.#....###.##.#.........#
##...#.###.#.#...#.#.##......###########
####.....###.#.###.#.#..#..#..#........#
#.....##.#...#.....#.##.#.############.#
#####..###.#########.#..#.#............#
#........#.#.........##.#.##.###.#####.#
#.###.##.#.#.#######..#.#..#.#.#.....#.#
#...#..#.#.#.#........#.####.#.#####.#.#
###.####.#.#.###.#.#..#......#.......#.#
#...#....#.#.....#######.#####.#####.#.#
###.#.#.##.#####.#.....#.......#.....#.#
#...###....###.#.#.#.#.###############.#
#.#...########.#.#.#.#.................#
###.#.#........#.#.#########.###########
#...#....#####.#.#...#.....#.......#...#
#.########...###.#.#.#.#####.#.###.#.###
#..........#.....#.#.........#...#....W#
########################################
*

########################################
#S+##  #     ###+++++++++++++    ##    #
##+#     # #   #+###### ### +### #  ####
# +# ### # # ###+#+++ ### ##+#         #
##+++# ### # #+++#+#+##++++++###########
####++   ### #+###+#+# +#  #  #        #
#    +## #   #+++++#+##+# ############ #
#####+ ### #########+# +# # +++++++++++#
#+++++   # #        +##+# ##+### #####+#
#+### ## # # #######+ #+#  #+# #     #+#
#+++#  # # # #  +++++ #+####+# ##### #+#
###+#### # # ###+# #  #++++++#       #+#
#  +#    # #    +####### ##### ##### #+#
###+# # ## #####+#     #       #     #+#
#  +###    ### #+# # # ###############+#
# #+  ######## #+# # #      +++++++++++#
###+# #        #+# #########+###########
#+++#    ##### #+#.. #   ..#+++++++#  .#
#+########+++###+#.# # ##### # ###+# ###
#++++++++++#+++++#.#         #   #++++W#
########################################

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe