#define MAXNUM        80/* 棧中最大元素個數 */
#define N 11 /*地圖的長度*/
#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int  x;/* 行下標 */
    int  y;/* 列下標 */
    int  d;/* 運動方向 */
} DataType;
struct SeqStack {          /* 順序棧類型定義 */
    int  t;             /* 指示棧頂位置 */
    DataType  s[MAXNUM];
};
typedef  struct SeqStack  *PSeqStack;    /* 順序棧類型的指針類型 */
PSeqStack  pastack;                    /* pastack是指向順序棧的一個指針變量 */
PSeqStack  createEmptyStack_seq( void ) {
    PSeqStack pastack;
    pastack = (PSeqStack)malloc(sizeof(struct SeqStack));
    if (pastack == NULL)
        printf("Out of space!! \n");
    else
        pastack->t = -1;
    return pastack;
}
int isEmptyStack_seq( PSeqStack pastack ) {
return pastack->t == -1;
}
/* 在棧中壓入一元素x */
void  push_seq( PSeqStack pastack, DataType x ) {
if( pastack->t >= MAXNUM - 1  
   printf( "Overflow! \n" );
    else {
        pastack->t++;
        pastack->s[pastack->t] = x;
    }
}
/* 刪除棧頂元素 */
void  pop_seq( PSeqStack pastack ) {
    if (pastack->t == -1 )
        printf( "Underflow!\n" );
    else
        pastack->t--;
}
/* 當pastack所指的棧不為空棧時，求棧頂元素的值 */
DataType  top_seq( PSeqStack pastack ) {
    return (pastack->s[pastack->t]);
}
void pushtostack(PSeqStack st, int x, int y, int d) {
    DataType element;
    element.x = x;
    element.y = y;
    element.d = d;
    push_seq(st, element);
}
void printpath(PSeqStack st) {
    DataType element;
    printf("The revers path is:\n");     /* 打印路徑上的每一點 */
    while(!isEmptyStack_seq(st)) {
        element = top_seq(st);
        pop_seq(st);
        printf("the node is: %d %d \n", element.x, element.y);
    }
}
/* 迷宮maze[M][N]中求從入口maze[x1][y1]到出口maze[x2][y2]的一條路徑 */
/* 其中 1<=x1,x2<=M-2 , 1<=y1,y2<=N-2 */
void mazePath(int maze[][N], int direction[][2], int x1, int y1, int x2, int y2) {
    int i, j, k, g, h;
    PSeqStack st;
    DataType element;
    st = createEmptyStack_seq( );
    maze[x1][y1] = 2;                      /* 從入口開始進入,作標記 */                    
    pushtostack(st, x1, y1, -1);           /* 入口點進棧 */

    while ( !isEmptyStack_seq(st)) {       /* 走不通時,一步步回退 */
        element = top_seq(st);
        pop_seq(st);
        i = element.x; j = element.y; 
        for (k = element.d + 1; k <= 3; k++) {           /* 依次試探每個方向 */
            g = i + direction[k][0];h = j + direction[k][1];
            if (g == x2 && h == y2 && maze[g][h] == 0) { /* 走到出口點 */
                printpath(st);            /* 打印路徑 */
                return;
            }
            if (maze[g][h] == 0) {        /* 走到沒走過的點 */
                maze[g][h] = 2;           /* 作標記 */
                pushtostack(st, i, j, k); /* 進棧 */
                i = g; j = h; k = -1;     /* 下一點轉換成當前點 */
            }
        }
    }
    printf("The path has not been found.\n");/* 棧退完未找到路徑 */
}
 int main()
 {
    int i,j,k;
              int maze[][N] = {
        1,1,1,1,1,1,1,1,1,1,1,
        1,0,1,0,0,1,1,1,0,0,1,
        1,0,0,0,0,0,1,0,0,1,1,
        1,0,1,1,1,0,0,0,1,1,1,
        1,0,0,0,1,0,1,1,0,1,1,
        1,1,0,0,1,0,1,1,0,0,1,
        1,1,1,0,0,0,0,0,0,0,1,
        1,1,1,1,1,1,1,1,1,1,1
         };

   int driection[4][2]= {0,1,1,0,0,-1,-1,0};
   printf("\n");
  for(i=0;i<= 7;i++)
  {
     k=0;
     for(j=0;j<=10;j++)
     {
       k++;
       printf("%5d",maze[i][j]);
       if(k==11)
         printf("\n");

        }
   }
   mazePath(maze,driection,1,1,6,9);
  getchar();
  return 0;
  }