#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <ctime>
#include <windows.h>
#define N 5
using namespace std;
bool WIN=false;
struct labirint
{
int s;
bool bil;
};
struct coordinate
{
int i;
int j;
};
struct labirint setka[N][N];
class Stack
{
private:
int top; //номер последнего элемента
int n; // количество элементов всего
struct coordinate *s;
public:
Stack(int k=100)
{
n = k;
s = new struct coordinate[n];
top = -1; // сперва список пустой
}
~Stack()
{
delete[] s;
}
int PUSH(int i, int j) //добавление элемента
{
//проверяем на полноту
if(FULL()) return 0;
s[++top].i=i;
s[top].j=j;
cout<<"gjjgjg";
return 1;
}
int POP(struct coordinate *x)//снятие элемента с его удалением из стека
{
//проверяем пуст ли стек
if(EMPTY())
return 0;
if(x)
*x=s[top];
top--;
return 1;
}
int EMPTY (void) // проверка стека на пустоту
{
if(top==-1)
return 1;
return 0;
}
int FULL (void) //проверка на полноту
{
if(top==n-1)
return 1;
return 0;
}
int TOP (struct coordinate *x) // посмотреть на последний элемент ( без удаления)
{
//проверка стека
*x=s[top];
}
};
void poisk_vixoda(int i, int j, Stack *Lab)
{
setka[i][j].bil=true;
Lab->PUSH(i,j);
if( (i==(N-1)) && (j==(N-1)) )
{
WIN=true;
return ;
}
if( (i>=0 && i<N) && (j+1>=0 && j+1<N) && !WIN )
if(!setka[i][j+1].s && !setka[i][j+1].bil )
poisk_vixoda( i, j+1,Lab);
if( (i+1>=0 && i+1<N) && (j>=0 && j<N) && !WIN )
if(!setka[i+1][j].s && !setka[i+1][j].bil)
poisk_vixoda(i+1, j,Lab);
if( (i>=0 && i<N) && (j-1>=0 && j-1<N) && !WIN )
if(!setka[i][j-1].s && !setka[i][j-1].bil)
poisk_vixoda( i, j-1,Lab);
if( (i-1>=0 && i-1<N) && (j>=0 && j<N) && !WIN )
if(!setka[i-1][j].s && !setka[i-1][j].bil)
poisk_vixoda( i-1, j,Lab);
if(!WIN)
{
Lab->POP(NULL);
return;
}
}
int main()
{
SetConsoleCP(1251);// установка кодовой страницы win-cp 1251 в поток ввода
SetConsoleOutputCP(1251); // установка кодовой страницы win-cp 1251 в поток вывода
Stack stack(N*N);
struct coordinate temp;
char menu;
srand(time(NULL));
int i,j;
do
{
WIN=false;
system("cls");
cout<<"\n1. лабиринт 1\n";
cout<<"\n2. лабиринт 2\n";
cout<<"\n3. рандомный лабиринт\n";
cout<<"\n4. создать лабиринт самостоятельно\n";
cout<<"\n5. выход\n";
cout<<"\n выберите пункт меню: ";
cin>>menu;
switch(menu)
{
case '1':
for( i=0; i<N; i++)
for( j=0; j<N; j++)
{
if( !(i%2) )
setka[i][j].s=0;
else
setka[i][j].s=1;
setka[i][j].bil = false;
}
setka[1][4].s=setka[3][3].s=0;
break;
case '2':
{for ( i=0; i<N ; i++)
{
for ( j=0; j<N; j++)
{
setka[i][j].s =1;
setka[i][j].bil = false;
}
}
setka[0][0].s=setka[0][1].s=setka[0][3].s=setka[1][1].s=setka[1][2].s=setka[1][4].s=setka[2][2].s=setka[2][4].s=setka[4][2].s=setka[4][4].s=0;
i=3;
for(j=0; j<N;j++)
setka[i][j].s=0;
break;
}
case '3':
{
for ( i=0; i<N ; i++)
{
for ( j=0; j<N; j++)
{
setka[i][j].s = (rand() % 2 == 0)?1:0;
setka[i][j].bil = false;
}
}
setka[0][0].s=setka[N-1][N-1].s=0;
break;
}
case '4':
system("cls");
for(i=0; i<N ; i++)
{
cout<<"\n введите элементы "<<i<<" строки:\n" ;
for(j=0; j<N; j++)
{
cin>>setka[i][j].s;
setka[i][j].bil = false;
}
}
break;
}
if(menu!='5')
{
system("cls");
for(i=0; i<N; i++)
{
for(j=0; j<N; j++)
{
cout<<setka[i][j].s;
cout<<" ";
}
cout<<endl;
}
poisk_vixoda(0,0,&stack);
if(WIN)
{
while(!stack.EMPTY())
{
stack.POP(&temp);
cout<<"("<<temp.i<<","<<temp.j<<") ";
}
}
else
cout<<"\n лабиринт нельзя пройти\n";
system("PAUSE");
}
}
while(menu != '5');
return 0;
}