#include "stdafx.h"
#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;
return 1;
}
int POP(struct coordinate *x)//снятие элемента с его удалением из стека
{
//проверяем пуст ли стек
//if(EMPTY())
// return 0;
cout<<s[top].i<<s[top].j<<--top;
cout<<s[top].i<<s[top].j<<top;
//*x=s[top];
// top--;
return 1;
}
int pop2(struct coordinate *m)
{
if (m)
*m=s[top];
top--;
return 0;
}
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);
};
void Stack :: poisk_vixoda(int i, int j)
{
setka[i][j].bil=true;
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);
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);
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);
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);
if(!WIN)
{
pop2(NULL);
return;
}
}
int main()
{
SetConsoleCP(1251);// установка кодовой страницы win-cp 1251 в поток ввода
SetConsoleOutputCP(1251); // установка кодовой страницы win-cp 1251 в поток вывода
Stack stack(N*N);
char menu;
srand(time(NULL));
int i,j;
do
{
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)?0:1;
setka[i][j].bil = false;
}
}
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;
}
WIN=false;
system("cls");
for(i=0; i<N; i++)
{
for(j=0; j<N; j++)
{
cout<<setka[i][j].s;
cout<<" ";
}
cout<<endl;
}
stack.poisk_vixoda(0,0);
struct coordinate *temp;
temp = new struct coordinate;
if(WIN)
{
while(!stack.EMPTY())
{
stack.pop2(temp);
cout<<"("<<temp->i<<","<<temp->j<<") ";
}
}
else
cout << "Sorry, Mario..."<< endl;
system ("PAUSE");
}
while(menu != '5');
return 0;
}