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