#include<iostream>
#include<fstream>
using namespace std;
//Constant values about direction
#define DIRECTION 4
#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3
const int MOVE_X[DIRECTION]={0, 1, 0, -1};
const int MOVE_Y[DIRECTION]={-1, 0, 1, 0};
//Constant Values about maze[][] and mark[][]
#define SIZE_X 6
#define SIZE_Y 7
#define EMPTY 0
#define BLOCKED 1
#define MARKED 1
//Structure about stack
#define STACK_SIZE SIZE_X*SIZE_Y
struct Element
{//
int x;
int y;
int dir;
Element(int aX, int aY, int aDir)
{//Constructor with initial data
x=aX;
y=aY;
dir=aDir;
}
Element(){}//Default constructor
};
//Function about stack
void push(int * argTop, Element * argStack, Element item);
bool isEmpty(int argTop);
Element pop(int * argTop, Element * argStack);
void display(int argX, int argY, int argMaze[][SIZE_X+2]);
int main()
{
int maze[SIZE_Y+2][SIZE_X+2];
int mark[SIZE_Y+2][SIZE_X+2]={{0,},{0,1,}};
//Starting point is already marked
int top=-1;
//Assign maze with file IO
ifstream fin("mazeTxt.txt");
while(!fin.eof())
{//Until end of file
for(int y=0;y<SIZE_Y+2;y++){
for(int x=0;x<SIZE_X+2;x++){
fin>>maze[y][x];
if(maze[y][x]==BLOCKED)
maze[y][x]=BLOCKED;
else
maze[y][x]=EMPTY;
}
fin.get();
}
}
//Declare stack
Element stack[STACK_SIZE];
//Push the starting point into the stack
push(&top, stack, Element(1, 1, 1));
int y, x, dir;
int nextY, nextX;
while(!isEmpty(top))
{//Until stack is empty
Element temp=pop(&top, stack);
y=temp.y;
x=temp.x;
dir=temp.dir;
while(dir<=LEFT)
{
nextY=y+MOVE_Y[dir];
nextX=x+MOVE_X[dir];
if(nextY==SIZE_Y && nextX==SIZE_X)
{//Is in the end point?
display(nextX, nextY, maze);
push(&top, stack, Element(x, y, dir));
//Push the last movement to stack
for(int i=0;i<top+1;i++)
{//Print path from start to end
if(stack[i].dir==DOWN)
cout<<"DOWN ";
else if(stack[i].dir==UP)
cout<<"UP ";
else if(stack[i].dir==LEFT)
cout<<"LEFT ";
else
cout<<"RIGHT ";
}
cout<<endl;
return 0;
}
if(maze[nextY][nextX]==EMPTY && mark[nextY][nextX]==EMPTY)
{//The next position is available
display(x, y, maze);
mark[nextY][nextX]=MARKED;
push(&top, stack, Element(x, y, dir));
y=nextY;
x=nextX;
dir=UP;
}
else
{
dir++;
display(x, y, maze);
}
}
}
cout<<"There is no path in maze\n";
return 0;
}
void push(int *argTop, Element * argStack, Element item)
{//Insert the element into the stack
if(*argTop>=STACK_SIZE-1)
{
cout<<"Your stack is full now\n";
exit(1);
}
argStack[++(*argTop)]=item;
}
Element pop(int * argTop, Element * argStack)
{//Take the element from the stack
if(isEmpty(*argTop))
{
cout<<"Your stack is empty now\n";
exit(1);
}
else
return argStack[(*argTop)--];
}
bool isEmpty(int argTop)
{//Is the stack empty?
if(argTop==-1)
return true;
else
return false;
}
void display(int argX, int argY, int argMaze[][SIZE_X+2])
{//Show the maze and current position
system("cls");
for(int i=0;i<SIZE_Y+2;i++)
{
for(int j=0;j<SIZE_X+2;j++)
{
if(i==argY && j==argX)
cout<<"⊙";//Current Position
else if(argMaze[i][j]==0)
cout<<" ";//Path
else
cout<<"■";//Wall
}
cout<<endl;
}
}
