[C++] Prośba o pomoc/ocene - labirynt i rekurencja

0

Napisałem program który szuka sobie wyjścia z labiryntu.
Jako, że nie jestem zbytnio zaawansowany jeśli chodzi o rozwiązywanie takich problemów (że o rekurencji nie wspomnę) bardzo bym prosił o jakieś odniesienie się do tego - bo sobie jakoś nie ufam, co prawda sprawdzałem trochę ten program i znajduje wyjście - ale jak już napisałem nie wiem czy to co zrobiłem jest do końca poprawne - nie umiem tego ocenić.

założenia
1 - Labirynt jest wczytywany z pliku tekstowego (dla ułatwienia ma wymiar 20x20)
2 - oznaczenia w pliku tekstowym reprezentującym labirynt 1-ściana 2-korytarz 3-wyjście
3 - z labiryntu może być więcej niż jedno wyjście
4 - droga w labiryncie jest szerokości 1 znaku(nie mozna chodzic na skos)

sam program wygląda tak

MAIN.CPP

#include <iostream>
#include <conio.h>
#include "labirynt.h"
using namespace std;

int main(void)
{
  bool setXY=false;
  labirynt lab;
  while(!setXY)
  {
      setXY=lab.wskazStart();
      system("cls");         
  }
  lab.pokazLabirynt() ;
  getch();
  system("cls");
  lab.szukajDrogi(-1,-1,0);
  getch();
  
  return 1;
}

LABIRYNT.H

class labirynt
{
      private:
        int pozX, pozY, maxX, maxY;
        char **lab;
        bool czyLabirynt;
      public:
        labirynt();
        void pokazLabirynt();  
        bool wskazStart();  
        void szukajDrogi(int,int,int);
        ~labirynt();            
};

LABIRYNT.CPP

#include <iostream>
#include <fstream>
#include <conio.h>
#include "labirynt.h"
using namespace std;

labirynt::labirynt()
{
  maxX=20;
  maxY=20;
  fstream plik;
  char t;
  czyLabirynt=true;
  plik.open("labirynt.txt",ios::in);  
  if(!plik)
  {
     czyLabirynt=false;
     cout<<"BLAD ZALADOWANIA PLIKU LABIRYNTU"<<endl;
  }
  if(czyLabirynt)
  {
      int i=0,j=0;
      char t;
      lab = new char*[maxY];
      lab[0]=new char[maxX];
      while(!plik.eof())
      {
        plik.get(t);
        if((int)t==10)    
        {
           i++;j=0;
           lab[i]=new char[maxX];
           continue;                
        }
        lab[i][j]=t;
        j++;
      } 
  }
  plik.close();   
}

void labirynt::pokazLabirynt()
{
   if(!czyLabirynt)
   {
        cout<<"NIE WCZYTANO PLIKU NIE MA CZEGO OGLADAC"<<endl;
        return;
   }    
   int i,j; 
   char t;    
   for(i=0;i<maxX;i++)
   {
      for(j=0;j<maxX;j++)                 
      {
          t=lab[i][j];
          if(t=='2')               
           cout <<" ";//(char)254;     
          else if(t=='1') 
           cout <<(char)177;     
          else if(t=='3')  
           cout <<(char)248;
          else if(t=='4')  
           cout <<(char)227;
          else 
            cout <<t;
      }
      cout<<"\n";
  }
  cout<<"*******LEGENDA********"<<endl;
  cout<<(char)177<<" - SCIANA"<<endl;
  cout<<(char)248<<" - WYJSCIE"<<endl;
  cout<<(char)227<<" - START"<<endl;
}

bool labirynt::wskazStart()
{
     
  if(!czyLabirynt)
  {
       cout<<"NIE WCZYTANO PLIKU NIE MA GDZIE I CZEGO SZUKAC"<<endl;
       return false;
  }     
  int x,y;
  cout<<"Wskaz punt startu okreslajac jego wspolzedne X i Y"<<endl;
  cout<<"Podaj wspolzedna X: ";
  cin>>x;
  cout<<"Podaj wspolzedna Y: ";
  cin>>y;
  if((x-1<0 or x-1>maxX-1) or (y-1<0 or y-1>maxY-1))
  {
    cout<<"PODALES NIEWLASCIWY ZAKRES"<<endl;
    getch();
    return false;      
  }
  else
  {
      if(lab[y-1][x-1]=='2')
      {
         pozX=x-1;
         pozY=y-1;
         lab[y-1][x-1]='4';
         return true;
      }   
      else      
      {
         cout<<"TRAFILES W W SCIANE"<<endl;
         getch();
         return false;          
      } 
  }
  
}

///FUNKCJA SZUKAJĄCA DROGI W LABIRYNCIE
void labirynt::szukajDrogi(int x,int y,int straz)
{
  static int pY,pX, find;
  int moz=0,biezX,biezY,str;
  if(find==1)
      return; 
  system("cls");         
  pokazLabirynt();
  str=straz+1;
  if(x==-1 or y==-1)
    x=pozX,y=pozY;
   pX=x;
   pY=y; 
  while(moz<4)//dla danej opozycji mogą być max 4 drogi (góra dół lewo prawo)
  {
     //okreslenie mozliwej pozycji wzgledem bieżącego położenia pozycji 
     if(moz==0)
     {
        biezX=x;
        biezY=y-1;
     }              
     else if(moz==1)
     {
        biezX=x+1;
        biezY=y;
     }              
     if(moz==2)
     {     
        biezX=x;
        biezY=y+1;
     }              
     if(moz==3)
     {
        biezX=x-1;
        biezY=y;
     }
     //jeśli bieżąca pozycja wykracza poza labirynt to bierz następną  
     if((biezX<0 or biezX>maxX-1) or (biezY<0 or biezY>maxY-1))
     {
       moz++;                       
       continue;
     }
     else
     {
         //jesli nie wykracza i jest drogą to nią idź
         if(lab[biezY][biezX]=='2')
         { 
           lab[biezY][biezX]='.';
           szukajDrogi(biezX,biezY,str);
         }  
         //jesli nie wykracza i jest jakimś wyjściem to znalałes wyjście
         else if(lab[biezY][biezX]=='3')
         {
           cout<<"WYJSCIE !!!!"<<endl;
           getch();  
           find=1;
           return;
        }
        moz++;     
     }         
  }           
  
           
}
labirynt::~labirynt()
{
    if(!czyLabirynt)
        return;
    for(int i=0;i<maxY;i++)
        delete []  lab[i];
    delete [] lab;                  
}

przykładowe labirynty

11111111111111111111
12222222212222222221
12121111211211211121
13122222222222222221
12111211211121212121
12111211222222222221
12111222211212112121
12111211211211212121
12111211211222222121
12222222211211112121
12111211222222222221
12222222212121121111
12111211212121121111
12222222212121121111
12112111211121121111
12222222222222222211
11121121211121211211
11121121211121211211
11122221211122222231
1111111111111111111
11111111111111111111
12222222212222222221
12111111211111111121
13122222222222222221
12111211211111112121
12111211222222222221
12111211211211112121
12111211211211112121
12111211211211112121
12222222211211112121
12111211222222222221
12111211211121121111
12111211211121121111
12222222211121121111
12111111211121121111
12222222222222222211
11121121211121111211
11121121211121111211
11122221211122222231
1111111111111111111
0

No raczej nie będzie działać dobrze. A rekurencje zastosowałeś :) ! w tej linijce

szukajDrogi(biezX,biezY,str);

A nie będzie działać dobrze np w takim labiryncie

11111
12221
12122 - wyjscie
12221
11211
11211
|
wejscie

bo zaczniesz się kręcić w kółko, dlatego, że algorytm najpierw próbuje iść w dół i zawsze ominie wyjście.

Potrzebujesz DFS (Deep First Search) czyli przeszukiwanie grafu w głąb. Musisz oznaczać pola już odwiedzone.

0

dzięki za odpowiedź

trochę nad tym sam posiedziałem i zrobiłem coś takiego
potestowałem i wygląda na to, że wszystko jest OK - dodałem sprawdzanie czy labirynt ma osiągalne wyjście oraz losowy kierunek (nie ma schematu np góra, prawo, dół lewo)

może się komuś przyda
może ktoś będzie miał jakieś co do tego uwagi, że można to np lepiej zrobić

PLIK MAIN>CPP

#include <iostream>
#include <conio.h>
#include "labirynt.h"
using namespace std;

int main(void)
{
  bool setXY=false;
  labirynt lab;
  int wynikLab;
  while(!setXY)
  {
      setXY=lab.wskazStart();
      system("cls");         
  }
  lab.pokazLabirynt();
  wynikLab=lab.szukajDrogi(-1,-1);
  lab.pokazLabirynt();
  if(wynikLab==1)
  {
    cout<<"WYJSCIE "<<endl;
    lab.pokazWyjscie();
  }  
  else  
    cout<<"NIE MOZNA OSIAGNAC WYJSCIA LABIRYNTU "<<endl;    
  getch();
  
  return 1;
}

PLIK LABIRYNT.H

class labirynt
{
      private:
        int pozX, pozY, maxX, maxY, wyjscieX,wyjscieY,ilePoprzenich;
        int **tablicaPoprzednich;
        char **lab;
        bool czyLabirynt, czyWyjscie;

        int szukajNastepny(int [][2],int, int);
        void przesun(int [],int[][2],int, int, int);
        bool sprawdzSkrzyzowanie(int [][2], int, int, int);
        
        void tworzTablicePoprzednich(int,int);
        void usunTablicePoprzednich();
        
        void usunPunktPowrotu(int);
        
      public:
        labirynt();
        void pokazLabirynt();  
        bool wskazStart();  
        int szukajDrogi(int,int);
        void pokazWyjscie();
        ~labirynt();            
};

PLIK LABIRYNT.CPP

#include <iostream>
#include <fstream>
#include <conio.h>
#include "labirynt.h"
using namespace std;

labirynt::labirynt()
{
  maxX=20;
  maxY=20;
  fstream plik;
  char t;
  czyLabirynt=true;
  plik.open("lab2.txt",ios::in);  
  if(!plik)
  {
     czyLabirynt=false;
     cout<<"BLAD ZALADOWANIA PLIKU LABIRYNTU"<<endl;
  }
  if(czyLabirynt)
  {
      int i=0,j=0;
      char t;
      lab = new char*[maxY];
      lab[0]=new char[maxX];
      while(!plik.eof())
      {
        plik.get(t);
        if((int)t==10)    
        {
           i++;j=0;
           lab[i]=new char[maxX];
           continue;                
        }
        lab[i][j]=t;
        j++;
      } 
  }
  plik.close();   
  czyWyjscie=false;
}

void labirynt::pokazLabirynt()
{
   if(!czyLabirynt)
   {
        cout<<"NIE WCZYTANO PLIKU NIE MA CZEGO OGLADAC"<<endl;
        return;
   }    
   int i,j; 
   char t;    
   for(i=0;i<maxX;i++)
   {
      for(j=0;j<maxX;j++)                 
      {
          t=lab[i][j];
          if(t=='2')               
           cout <<" ";//(char)254;     
          else if(t=='1') 
           cout <<(char)177;     
          else if(t=='3')  
           cout <<(char)248;
          else if(t=='4')  
           cout <<(char)227;
          else 
            cout <<t;
      }
      cout<<"\n";
  }
  cout<<"*******LEGENDA********"<<endl;
  cout<<(char)177<<" - SCIANA"<<endl;
  cout<<(char)248<<" - WYJSCIE"<<endl;
  cout<<(char)227<<" - START"<<endl;
}

bool labirynt::wskazStart()
{
     
  if(!czyLabirynt)
  {
       cout<<"NIE WCZYTANO PLIKU NIE MA GDZIE I CZEGO SZUKAC"<<endl;
       return false;
  }     
  int x,y;
  cout<<"Wskaz punt startu okreslajac jego wspolzedne X i Y"<<endl;
  cout<<"Podaj wspolzedna X: ";
  cin>>x;
  cout<<"Podaj wspolzedna Y: ";
  cin>>y;
  if((x-1<0 or x-1>maxX-1) or (y-1<0 or y-1>maxY-1))
  {
    cout<<"PODALES NIEWLASCIWY ZAKRES"<<endl;
    getch();
    return false;      
  }
  else
  {
      if(lab[y-1][x-1]=='2')
      {
         pozX=x-1;
         pozY=y-1;
         lab[y-1][x-1]='4';
         return true;
      }   
      else      
      {
         cout<<"TRAFILES W W SCIANE"<<endl;
         getch();
         return false;          
      } 
  }
  
}
int labirynt::szukajDrogi(int x,int y)
{
     static int biezX, biezY, wynik;
     int mozliweRuchy[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
     int nstRuch, pozNstRuch[2], wywolanieX, wywolanieY;
     if(x==-1 && y ==-1)
     {
        biezX=pozX;
        biezY=pozY;         
        tablicaPoprzednich = new int*[1];
        tablicaPoprzednich[0] = new int[2];
        tablicaPoprzednich[0][0] = biezX;
        tablicaPoprzednich[0][1] = biezY;
        ilePoprzenich=1;
        wynik=0;
     }
     else
     {
        biezX=x;
        biezY=y;  
     }
     nstRuch=szukajNastepny(mozliweRuchy,biezX,biezY);
     if (czyWyjscie)
     {
      wynik = 1;    
     }
     while(!wynik)
     {
         if(nstRuch<4)
         {
            przesun(pozNstRuch,mozliweRuchy,biezX,biezY,nstRuch);
            if(sprawdzSkrzyzowanie(mozliweRuchy,pozNstRuch[0],pozNstRuch[1],1))
            {
                tworzTablicePoprzednich(pozNstRuch[0],pozNstRuch[1]); 
                ilePoprzenich++;
                 
            }
            wywolanieX=pozNstRuch[0];
            wywolanieY=pozNstRuch[1];
         }
         else
         {
           int szukX,szukY;
           while(ilePoprzenich>0)
           {
                szukX=tablicaPoprzednich[ilePoprzenich-1][0];
                szukY=tablicaPoprzednich[ilePoprzenich-1][1];
                if(sprawdzSkrzyzowanie(mozliweRuchy,szukX,szukY,0))
                {
                    wywolanieX = szukX;                              
                    wywolanieY = szukY; 
                    break;
                }
                else
                {
                    usunPunktPowrotu(ilePoprzenich);
                    ilePoprzenich--;                                                              
                }  
           }
         }
         if(ilePoprzenich<1)
            wynik =-1;               
         else   
         {
           pokazLabirynt();
           system("cls");
           szukajDrogi(wywolanieX,wywolanieY);    
         }  
         
     }
     return wynik;
}
int labirynt::szukajNastepny(int ruchy[][2],int x, int y)
{
    int ruch=0, sprX, sprY, ruchTmp[4], z=0, zmienna;
    while (ruch<4)
    {
       sprX=x + ruchy[ruch][0];
       sprY=y + ruchy[ruch][1];
       if((sprX<0 || sprX>maxX)|| (sprY<0 || sprY>maxY))
       {
         ruch++;
         continue;         
       }
       if(lab[sprY][sprX]=='3')
       {
          wyjscieX = sprX;
          wyjscieY = sprY;
          czyWyjscie=true;
          break;                     
       }
       if(lab[sprY][sprX]=='2')
       {
          z++;
          ruchTmp[z-1]=ruch;                     
          
       }
       ruch++;
    }
    if(z==0)
        return ruch;
    srand(time(NULL));
    zmienna=(rand()%z)  ;
    return ruchTmp[zmienna];
}
void labirynt::przesun(int tablica[],int ruchy[][2], int x, int y, int index)
{
      tablica[0]=x + ruchy[index][0];
      tablica[1]=y + ruchy[index][1];
      lab[tablica[1]][tablica[0]] = '.';

}
bool labirynt::sprawdzSkrzyzowanie(int tablica[][2],int x, int y, int wielkosc)
{
     int mozliwosci = 0;
     char z;
     for(int i=0;i<4;i++)
     {
       z=lab[y + tablica[i][1]][x + tablica[i][0]];
       if( z == '2' || z == '3')  
          mozliwosci++; 
     }

     if(mozliwosci>wielkosc)
         return true;
     return false; 
    
}

void labirynt::tworzTablicePoprzednich(int x, int y)
{
     int **tmpTP; 
    
     tmpTP = new int*[ilePoprzenich];
    
     for(int i=0;i<ilePoprzenich;i++)
     {
        tmpTP[i]=new int[2];
        tmpTP[i][0] = tablicaPoprzednich[i][0];    
        tmpTP[i][1] = tablicaPoprzednich[i][1];    
     }     
          
     usunTablicePoprzednich();
     tablicaPoprzednich = new int*[ilePoprzenich+1];
     for(int i=0;i<ilePoprzenich;i++)
     {
        tablicaPoprzednich[i]=new int[2];
        tablicaPoprzednich[i][0] = tmpTP[i][0];    
        tablicaPoprzednich[i][1] = tmpTP[i][1]; 
     }
     tablicaPoprzednich[ilePoprzenich]=new int[2];  
     tablicaPoprzednich[ilePoprzenich][0]=x;  
     tablicaPoprzednich[ilePoprzenich][1]=y; 
     
    
     for(int i=0;i<ilePoprzenich;i++)
     {
        delete [] tmpTP[i];        
     }
     delete [] tmpTP;

}
void labirynt::usunTablicePoprzednich()
{
  for(int i=0;i<ilePoprzenich;i++)
  {
      delete [] tablicaPoprzednich[i];        
  }
  delete [] tablicaPoprzednich;
}
void labirynt::usunPunktPowrotu(int index)
{
  delete [] tablicaPoprzednich[index-1];           
}
void labirynt::pokazWyjscie()
{
 cout<<"WSPOLZEDNE WYJSCIA"<<endl;
 cout<<"X="<<wyjscieX+1<<endl;
 cout<<"Y="<<wyjscieY+1<<endl;     
}

labirynt::~labirynt()
{
    if(!czyLabirynt)
        return;
    usunTablicePoprzednich();    
    for(int i=0;i<maxY;i++)
        delete []  lab[i];
    delete [] lab;                  
}
0

nie wiem co jest ale gdy nie znaleziono u mnie pliku to blue screen mi wyskoczył :-[

0

no łatwo wpaść "co".
funkcje szukajDrogi, szukajNastepny i kilka innych, nie zawierają już sprawdzenia:
if(!czyLabirynt) ....
więc ruszają i latają po niezainicjalizowanym obiekcie.

btw: blue screen, to ktoś jeszcze Windows 9x używa w roku 2007? :O

1 użytkowników online, w tym zalogowanych: 0, gości: 1