Przechodzenie grafu metodą DFS - droga w labiryncie

// Demonstracja działania procedury DFS
// wykorzystanej do poszukiwania drogi
// w labiryncie.
//-------------------------------------
// (C)2011 Koło Informatyczne
// I LO w Tarnowie
//-------------------------------------

#include <iostream>
#include <string>
#include <ctime>
#include "newconio.h"

using namespace std;

// Stałe

const int PUSTE      =  0;  // pusta komora/korytarz
const int SCIANA     =  1;  // komórka zawierająca ścianę
const int W_LEWO     =  2;  // komórka z nitką w lewo
const int W_PRAWO    =  3;  // komora z nitką w prawo
const int W_GORE     =  4;  // komora z nitką w górę
const int W_DOL      =  5;  // komora z nitką w dół
const int ODWIEDZONE =  6;  // komora już odwiedzona, bez nitki

const int KROK       = 10;  // opóźnienie kroków w ms

const int LX         = 79;  // rozmiar labiryntu w poziomie = 1 + 2 * k
const int LY         = 47;  // rozmiar labiryntu w pionie

// Zmienne globalne

int labirynt[LX][LY];       // labirynt
int xs,ys;                  // współrzędne punktu startowego
int xk,yk;                  // współrzędne punktu końcowego
int xp,yp;                  // współrzędne poszukiwacza drogi
int lk;                     // licznik kroków poszukiwacza

// Funkcja wyświetla przekazany jej tekst na środku ostatniego
// wiersza ekranu, oczekuje na wciśnięcie przez użytkownika
// klawisza i zwraca jego kod.
//------------------------------------------------------------

int czekaj(string t)
{
  int klawisz;

  fillrect(' ',0xf0,0,49,79,49);
  textcolor(RED); textbackground(WHITE);
  center(49,_pl(t));

  while(!(klawisz = getch()));

  return klawisz;
}

// Funkcja tworzy labirynt w tablicy labirynt
//-------------------------------------------

void tworz_labirynt()
{
  int x,y,c;

  // wypełniamy cały labirynt ścianami;

  for(x=0; x<LX; x++)
    for(y=0; y<LY; y++) labirynt[x][y] = SCIANA;

  // tworzymy komory i korytarze. Komory tworzone są co 2 komórki.
  // Korytarze łączą komory z lewej i z góry

  for(x=1; x<LX; x+=2)
    for(y=1; y<LY; y+=2)
    {
        labirynt[x][y] = PUSTE;        // komora
        c = 0;                         // licznik korytarzy
        if(rand() % 3 == 0)
        {
            if(x > 1)
              labirynt[x-1][y] = PUSTE; // korytarz z lewej
            c++;                        // zwiększamy licznik korytarzy
        }
        if(rand() % 3 == 0)
        {
            if(y > 1)
              labirynt[x][y-1] = PUSTE;  // korytarz z góry
            c++;                         // zwiększamy licznik korytarzy
        }
        if(c == 0)                     // jeśli nie został utworzony korytarz,
        {                              // tworzymy go z lewej albo u góry
            if(rand() % 2)
            {
                if(x > 1) labirynt[x-1][y] = PUSTE;
            }
            else
            {
                if(y > 1) labirynt[x][y-1] = PUSTE;
            }
        }
    }

    // zerujemy współrzędne początku, końca ścieżki, poszukiwacza
    // oraz licznik kroków

    xs = ys = xk = yk = xp = yp = lk = 0;
}

// Procedura wyświetla labirynt na ekranie
//----------------------------------------

void pokaz_labirynt()
{
    int x,y,rxs,rxk,rys,ryk;

    if(xp)                      // jeśli poszukiwacz jest w labiryncie,
    {
        rxs = xp-1; rxk = xp+1; // to wyświetlimy tylko fragment
        rys = yp-1; ryk = yp+1; // wokół niego - reszta labiryntu już wyświetlona
    }
    else
    {
        rxs = 0; rxk = LX-1;
        rys = 0; ryk = LY-1;
    }

    for(x = rxs; x <= rxk; x++)
      for(y = rys; y <= ryk; y++)
        switch(labirynt[x][y])
        {
            case PUSTE      : putxy(' ',0xe0,x,y); break;
            case SCIANA     : putxy(' ',0x10,x,y); break;
            case ODWIEDZONE : putxy(' ',0xf0,x,y); break;
            default         : putxy(' ',0x40,x,y); break;
        }

     if(xp + yp > 0) putxy('P',0xe4,xp,yp);  // Poszukiwacz
     if(xs + ys > 0) putxy('S',0x0c,xs,ys);  // Start
     if(xk + yk > 0) putxy('K',0x0a,xk,yk);  // Koniec

     if(lk)                                  // Licznik kroków
     {
         gotoxy(0,48);
         textattr(0x0e);
         cout << _pl("Liczba kroków : ");
         textcolor(LIGHTRED);
         cout << lk;
     }
}

// Procedura umożliwia użytkownikowi wybranie
// pozycji startowej i końcowej w labiryncie
//------------------------------------------

void ustaw_start_koniec(string t,int & x, int & y)
{
    x = y = 1;                             // rozpoczynamy w lewym górnym rogu

    while(true)
    {
        pokaz_labirynt();                  // wyświetlamy labirynt

        switch(czekaj(t))                  // czekamy na klawisz
        {                                  // i przesuwamy punkt wg klawisza
            case 72:  if(y > 1) y -= 2;    // w górę
                      break;
            case 77:  if(x < LX-2) x += 2; // w w prawo
                      break;
            case 80:  if(y < LY-2) y += 2; // w dół
                      break;
            case 75:  if(x > 1) x -= 2;    // w lewo
                      break;
            case 13:  return;              // klawisz ENTER kończy
        }
    }
}

// Procedura DFS szukająca drogi w labiryncie
// od punktu startowego do punktu końcowego
//-------------------------------------------

void szukaj_wyjscia()
{
  fillrect(' ',0xf0,0,49,79,49);
  textcolor(BLACK); textbackground(WHITE);
  center(49,_pl("Poszukiwanie ścieżki do punktu końcowego"));

  xp = xs;  // ustawiamy poszukiwacza w punkcie startowym
  yp = ys;

  labirynt[xp][yp] = ODWIEDZONE; // zaznaczamy tę komórkę jako odwiedzoną

  // DFS

  while(true)
  {
      lk++;                     // zwiększamy licznik
      pokaz_labirynt();         // wyświetlamy labirynt (fragment)
      delay(KROK);              // odczekujemy

      if(xp == xk && yp == yk)  // jeśli w punkcie końcowym, kończymy
      {
          putxy('K',0xf4,xp,yp);
          return;
      }

      // droga w lewo?

      if(labirynt[xp-1][yp] == PUSTE)
      {
          xp--;                      // przechodzimy w lewo
          labirynt[xp][yp] = W_LEWO; // rozwijamy nić w lewo
          continue;                  // wracamy na początek pętli
      }

      // brak drogi w lewo. Droga w górę?

      if(labirynt[xp][yp-1] == PUSTE)
      {
          yp--;                      // przechodzimy w górę
          labirynt[xp][yp] = W_GORE; // rozwijamy nić w górę
          continue;                  // wracamy na początek pętli
      }

      // w lewo i w górę brak drogi. Droga w prawo?

      if(labirynt[xp+1][yp] == PUSTE)
      {
          xp++;                       // przechodzimy w prawo
          labirynt[xp][yp] = W_PRAWO; // rozwijamy nić w prawo
          continue;                   // wracamy na początek pętli
      }

      // w lewo, w górę i w prawo brak drogi. Droga w dół?

      if(labirynt[xp][yp+1] == PUSTE)
      {
          yp++;                     // przechodzimy w dół
          labirynt[xp][yp] = W_DOL; // rozwijamy nić w dół
          continue;                 // wracamy na początek pętli
      }

    // nie udało się pójść w żadnym z dostępnych kierunków, gdyż
    // albo była tam ściana, albo już tam byliśmy. Próbujemy zatem
    // cofnąć się po nici do poprzedniego segmentu labiryntu.

    switch(labirynt[xp][yp])
    {
        case ODWIEDZONE : return;  // wróciliśmy na początek - brak ścieżki.
        case W_LEWO     : labirynt[xp++][yp] = ODWIEDZONE; break;
        case W_PRAWO    : labirynt[xp--][yp] = ODWIEDZONE; break;
        case W_GORE     : labirynt[xp][yp++] = ODWIEDZONE; break;
        case W_DOL      : labirynt[xp][yp--] = ODWIEDZONE; break;
    }
  }
}

int main()
{
    _cinit();
    srand(time(NULL));
    fullscreen(true);
    cursoroff();
    tworz_labirynt();
    ustaw_start_koniec("Wybierz punkt startowy i naciśnij ENTER",xs,ys);
    ustaw_start_koniec("Wybierz punkt końcowy i naciśnij ENTER",xk,yk);
    szukaj_wyjscia();
    czekaj("Koniec przejścia. Naciśnij dowolny klawisz, aby zakończyć program.");
    textattr(7);
    cursoron();
    fullscreen(false);
    return 0;
}