#include<iostream.h>
#include<stdlib.h>
#define MAXROW 100
#define MAXCOL 100

struct stack_node
{
	int x,y;
	struct stack_node *next;
};

typedef struct stack_node stack_list;
typedef stack_list *link;
link path=NULL;
//創建迷宮
void createmaze(int maze[MAXROW][MAXCOL],int row,int col )
{
	int i,j;
	for(i=0;i<row;i++)
	{
		for(j=0;j<col;j++)
		{
			if(j==0||j==col-1)
				maze[i][j]=1;
		}
	}
	for(j=0;j<col;j++)
	{
		for(i=0;i<row;i++)
		{
			if(i==0||i==row-1)
				maze[i][j]=1;
		}
	}
	cout<<"================================="<<endl;
	cout<<endl<<"創建迷宮,";
	cout<<"請輸入"<<row-2<<"*"<<col-2<<"大小的迷宮"<<endl;
	for(i=1;i<=row-2;i++)
	{
		for(j=1;j<=col-2;j++)
		{
			cin>>maze[i][j];
		}
	}
	cout<<endl;
	cout<<"迷宮圖為:"<<endl;
	for(i=0;i<row;i++)
	{
		for(j=0;j<col;j++)
		{
			cout<<maze[i][j]<<"  ";
		}
		cout<<endl;
	}
}
//棧數據的存入
link push(link stack,int x,int y)
{
	link newnode;
	newnode=(link)malloc(sizeof(stack_list));
	if(!newnode)
	{
		cout<<"內存分配失敗!";
		return NULL;
	}
	newnode->x=x;
	newnode->y=y;
	newnode->next=stack;
	stack=newnode;
	return stack;
}

//棧數據的取出
link pop(link stack,int *x,int *y)
{
	link top;
	if(stack!=NULL)
	{
		top=stack;
		stack=stack->next;
		*x=stack->x;
		*y=stack->y;
		delete top;
		return stack;
	}
	else *x=-1;
}

void main()
{		
	cout<<endl<<endl<<"==========================="<<endl;
	cout<<"0表示通路"<<endl;
	cout<<"1表示墻壁"<<endl;
	cout<<"2表示走過的路"<<endl;
	cout<<"3表示回溯的路"<<endl;
	cout<<"搜索方向下-〉右-〉上-〉左"<<endl;
	cout<<"==========================="<<endl;
	int maze[MAXROW][MAXCOL];
	int row,col;
	cout<<"請輸入迷宮行數和列數(迷宮最外面一層為墻壁):";
	cin>>row>>col;
	createmaze(maze,row,col);
	int i,j;
	int x,y;
	int m,n;
	cout<<"請輸入迷宮的入口坐標：";
	cin>>x>>y;
	cout<<"請輸入迷宮的出口坐標：";
	cin>>m>>n;
	while(x!=m||y!=n)
	{
		maze[x][y]=2;
		if(maze[x+1][y]<=0)                 //下
		{
			x=x+1;
			path=push(path,x,y);
		}
		else
			if(maze[x][y+1]<=0)               //右
			{
				y=y+1;
				path=push(path,x,y);
			}
			else
				if(maze[x-1][y]<=0)           //上
				{
					x=x-1;
					path=push(path,x,y);
				}
				else
					if(maze[x][y-1]<=0)         //左
					{
						y=y-1;
						path=push(path,x,y);
					}
					else
					{
						maze[x][y]=3;
						path=pop(path,&x,&y);
					}
	}
	maze[x][y]=2;
	cout<<"迷宮途徑如下所視:"<<endl;
	for(i=1;i<row-1;i++)
	{
		for(j=1;j<col-1;j++)
		{
			cout<<maze[i][j]<<"  ";
		}
		cout<<endl;
	}
}