#include"iostream.h"
#include"stdio.h"
#include"stdlib.h"
#define FALSE 0
#define ERROR 0
#define OK 1
#define TRUE 1
#define M 15
#define N 15 
struct postype                                 //定義迷宮內點的坐標類型
{ 
	int  x1;
    int  y1;
};
struct SElemType    
{
	int x;                                     //x行
    int y;                                     //y列
    int d;                                     //d下一步的方向             
}; 
struct StackNode       
{
	SElemType  elem;
    struct StackNode  *next;
};
typedef StackNode *LinkStack;
                                               //所需函數
int InitStack(LinkStack &S)                    //構造空棧
{   
	S=NULL;
    return OK;
}
int StackEmpty(LinkStack S)                    //判斷棧是否為空
{              
	if(S==NULL)
       return TRUE;
    else 
       return FALSE;
}
int Push(LinkStack &S, SElemType e)            //壓入新數據元素
{              
	LinkStack p;
    p=(LinkStack)malloc(sizeof(StackNode));
    p->elem=e;
    p->next=S;
    S=p;
    return OK;
}
int Pop(LinkStack &S,SElemType &e)             //棧頂元素出棧
{             
	LinkStack p;
    if(!StackEmpty(S))
	{
		e=S->elem;
        p=S;
        S=S->next;
        free(p);
        return OK;
	}
    else
        return ERROR;
}
void MazePath(postype begin,postype end,int maze[M][N],int diradd[4][2]) 
{
	int i,j,d;int a,b;
    SElemType elem,e;
    LinkStack S1, S2;
    InitStack(S1);
    InitStack(S2);
    maze[begin.x1][begin.y1]=2;                //入口點作上標記
    elem.x=begin.x1;
    elem.y=begin.y1; 
    elem.d=-1;                                 //開始為-1
    Push(S1,elem);
    while(!StackEmpty(S1))                     //棧不為空 有路徑可走
	{
		Pop(S1,elem);
        i=elem.x;
        j=elem.y;
        d=elem.d+1;                            //下一個方向
        while(d<4)     
		{                                      //開始試探東南西北各個方向
			a=i+diradd[d][0];
            b=j+diradd[d][1];

            if(a==end.x1 && b==end.y1 && maze[a][b]==0)   //如果到了出口
			{
				elem.x=i;
                elem.y=j;
                elem.d=d;
                Push(S1,elem); 
                elem.x=a;
                elem.y=b;
                elem.d=886;                    //方向輸出為-1 判斷是否到了出口
                Push(S1,elem);  
                printf("\n0=東 1=南 2=西 3=北\n 方向為 886為則走出迷宮\n\n");
                while(S1)                      //逆置序列 并輸出迷宮路徑序列
				{
					Pop(S1,e);Push(S2,e);
				}
                while(S2)
				{
				    Pop(S2,e);
                    printf("-(%d,%d,%d)-",e.x,e.y,e.d);
				}
                printf("\n(行坐標,列坐標,方向)\n");
                return ;
			}
            if(maze[a][b]==0)                  //找到可以前進的非出口的點
			{ 
				maze[a][b]=2;                  //標記走過此點
                elem.x=i;
                elem.y=j;
                elem.d=d;      
                Push(S1,elem);                 //當前位置入棧
                i=a;                           //下一點轉化為當前點
                j=b;
                d=-1;
			}
            d++;
		}
	}
    printf("沒有找到可以走出此迷宮路徑\n"); 
}
void initmaze( int maze[M][N])
{                                              //輸入的迷宮
	int i,j;
    int m,n;                                   //迷宮行，列
    printf("請輸入迷宮的行數 m=");
    scanf("%d",&m);
    printf("請輸入迷宮的列數 n=");
    scanf("%d",&n);
    printf("\n請輸入迷宮的各行各列\n//空格隔開//\n0代表路，1代表墻\n",m,n); 
    for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
    scanf("%d",&maze[i][j]); 
    printf("^_^您建立的迷宮為^_^\n");
    for(i=0;i<=m+1;i++)                        //添加一圈外圍封閉墻
	{  
		maze[i][0]=1;
        maze[i][n+1]=1;
	}
    for(j=0;j<=n+1;j++)
	{
		maze[0][j]=1;
        maze[m+1][j]=1;
	}   
    for(i=0;i<=m+1;i++)                        //輸出迷宮
	{ 
		for(j=0;j<=n+1;j++)
        printf("%d ",maze[i][j]); 
        printf("\n");
	}
}
void main()
{   
	printf("                 *************************************\n");
	printf("                 **** 數據結構課程設計（迷宮問題）****\n");
	printf("                 ****** 專業： 計算機科學與技術 ******\n");
	printf("                 *********   班級： 06網絡  **********\n");
	printf("                 *********   學生：   陳長  **********\n");
	printf("                 *********   學號：061124084 *********\n");
	printf("                 *************************************\n");
    int t;
	do{
	int maze[M][N];
    postype begin,end;                         //begin,end入口和出口的坐標 
    int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; //行增量和列增量 方向依次為東西南北
    initmaze(maze);                            //建立迷宮
    printf("\no(∩_∩)o...o(∩_∩)o...\n\n");
    printf("輸入入口的橫坐標,縱坐標\n不大于15(逗號隔開)");   
    scanf("%d,%d",&begin.x1,&begin.y1);
    printf("\n輸入出口的橫坐標,縱坐標\n不大于15(用逗號隔開)");
    scanf("%d,%d",&end.x1,&end.y1);
    MazePath(begin,end,maze,add); 
    printf("是否繼續？是1 / 否0\n");
    scanf("%d",&t);
	}while(t==1);
}