미로찾기/영동

#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;
	}
}

1 1 1 1 1 1 1 1
1 0 1 1 0 1 1 1
1 0 0 1 0 1 1 1
1 1 0 0 0 1 1 1
1 1 1 0 0 0 1 1
1 0 0 0 1 1 1 1
1 1 0 1 0 0 0 1
1 0 0 0 0 1 0 1
1 1 1 1 1 1 1 1