#include <iostream.h>
#include <stdlib.h>
#define MAXSIZE 1024
#define M 1024
#define N 1024
int maze[M][N];//定義迷宮數(shù)組
typedef struct
{
	int x;
	int y;
}item;
item move[8];//定義方向變量數(shù)組
typedef struct
{
	int x,y,d;		//橫縱坐標(biāo)及方向
}datatype;
typedef struct
{
	datatype data[MAXSIZE];
	int top;
}Seqstack;
Seqstack *Init_Seqstack()//棧初始化
{
	Seqstack *s;
	s=new Seqstack;
	if(!s)
	{
		cout<<"空間不足!\n";
		return NULL;
	}
	else
	{
		s->top=-1;
		return s;
	}
}
int Empty_Seqstack(Seqstack *s)//判斷棧空
{
	if(s->top==-1)
		return 1;
	else
		return 0;
}
int Push_Seqstack(Seqstack *s,datatype x)//入棧
{
	if(s->top==MAXSIZE-1)
		return 0;
	else
	{
		s->top++;
		s->data[s->top]=x;
		return 1;
	}
}
int Pop_Seqstack(Seqstack *s,datatype *x)//出棧
{
	if(Empty_Seqstack(s))
		return 0;
	else
	{
		*x=s->data[s->top];
		s->top--;
		return 1;
	}
}
void creat(int maze[M][N],int m,int n)//創(chuàng)建迷宮
{
	int a,i,j;
	for(i=0;i<m+2;i++)//定義迷宮邊界
	{
		maze[0][i]=1;
		maze[m+1][i]=1;
	}
	for(j=0;j<n+2;j++)//定義迷宮邊界
	{
		maze[j][0]=1;
		maze[j][n+1]=1;
	}
	for(i=1;i<m+1;i++)//輸入迷宮數(shù)據(jù)
	{
		for(j=1;j<n+1;j++)
		{
			cout<<"請輸入第"<<i<<"行第"<<j<<"個數(shù)據(jù):";
			cin>>a;
			maze[i][j]=a;
		}
	}
	cout<<"所建迷宮為: \n";
	for(i=1;i<m+1;i++)//輸出所建迷宮
	{
		for(j=1;j<n+1;j++)
			cout<<maze[i][j]<<'\0';
		cout<<endl;
	}
}
void Init_move()//定義方向變量
{
	move[0].x=0;
	move[0].y=1;
	move[1].x=1;
	move[1].y=1;
	move[2].x=1;
	move[2].y=0;
	move[3].x=1;
	move[3].y=-1;
	move[4].x=0;
	move[4].y=-1;
	move[5].x=-1;
	move[5].y=-1;
	move[6].x=-1;
	move[6].y=0;
	move[7].x=-1;
	move[7].y=1;
}
int path(int m,int n,Seqstack *s,int a1,int a2,int b1,int b2)//尋找迷宮出口
{
	datatype temp;
	int x,y,d,i,j;
	temp.x=a1;
	temp.y=a2;//定義入口
	temp.d=-1;
	Push_Seqstack(s,temp);
	while(!Empty_Seqstack(s))
	{
		Pop_Seqstack(s,&temp);
		x=temp.x;
		y=temp.y;
		d=temp.d+1;
		while(d<8)
		{
			i=x+move[d].x;
			j=y+move[d].y;
			if(maze[i][j]==0)
			{
				temp.x=x;
				temp.y=y;
				temp.d=d;
				Push_Seqstack(s,temp);
				x=i;
				y=j;
				maze[x][y]=-1;
				if(x==b1&&y==b2)//判斷是否達到出口
					return 1;
				else
					d=0;
			}
			else
				d++;
		}
	}
	return 0;
}
void show(Seqstack *s,int b1,int b2)//輸出迷宮路徑
{
	int i=0;
	for(;i<s->top+1;i++)
		cout<<"("<<s->data[i].x<<","<<s->data[i].y<<")"<<"-->";
	cout<<"("<<b1<<","<<b2<<")"<<endl;
}
void main()
{
	Seqstack *s;
	int m,n,p,a1,a2,b1,b2;
	cout<<"請輸入迷宮的實際行、列：\n";
	cin>>m>>n;
	creat(maze,m,n);
	s=Init_Seqstack();
	Init_move();
	cout<<"請輸入迷宮的入口及出口(坐標(biāo)格式): \n";
	cin>>a1>>a2>>b1>>b2;
	p=path(m,n,s,a1,a2,b1,b2);
	
	if(p==1)
	{
		cout<<"迷宮有路,路徑為: \n";
		show(s,b1,b2);
	}
	else
		if(p==0)
			cout<<"迷宮無路\n";
		else
			cout<<"操作失敗!\n";
}