#define MAXNUM 100/* 棧中最大元素個數 */ 
#define N 11  /*地圖的第一維長度*/ 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.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) 
{   FILE *fp;
    if((fp=fopen("a.txt","w"))==NULL)
	{  
		printf("cannot open file\n");
		exit(0);
	}

    DataType element; 
	fputs("The revers path is:",fp);
    printf("The revers path is:\n"); /* 打印路徑上的每一點 */ 
    while(!isEmptyStack_seq(st))
	{ 
    element = top_seq(st); 
    pop_seq(st); 
	fprintf(fp,"(%d,%d)", element.x, element.y);
    printf("the node is: %d %d \n", element.x, element.y); 
	} 
    fclose(fp);
} 

/* 迷宮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) 
{  
	FILE *fp;
    if((fp=fopen("a.txt","w"))==NULL)
	{  
		printf("cannot open file\n");
		exit(0);
	}
   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); 
     
      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) 
		{ /* 走到出口點 */ 
             pushtostack(st, g, h, k); /* 進棧 */
             printpath(st); /* 打印路徑 */ 
          return; 
		} 
        if (maze[g][h] == 0) { /* 走到沒走過的點 */ 
         maze[g][h] = 2; /* 作標記 */ 
         pushtostack(st, g, h, k); /* 進棧 */ 
         i = g; j = h; k = -1; /* 下一點轉換成當前點 */ 
		}
	  }
	   pop_seq(st); 
   } 
    fputs("The path has not been found.\n",fp);
    printf("The path has not been found.\n");/* 棧退完未找到路徑 */ 
    fclose(fp);
} 
                                             
#define M 8
#define N 11
void Creatmaze(int maze[M][N])
{
    int i, j;
	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;
	}
      srand( (unsigned)time( NULL ) );//初始化隨機數
      for(i=1;i<=M-2;i++)
	  {
		for(j=1;j<=N-2;j++)
        maze[i][j]  = rand() % 2; 
	  }
		for(i=0;i<=M-1;i++)
		{
		   for(j=0;j<=N-1;j++)
           printf("%6d",maze[i][j]);
		   printf("\n");
		}
		printf("\n");
}
int menv_select()
{
int s;
printf("請選擇：\n");
printf("0.退出\n");
printf("1.隨機生成迷宮\n");
printf("2.自定義\n");
for(;;)
{
	scanf("%d",&s);
if (s<0||s>2)
  printf("輸入錯誤，請重新輸入");
else
break;
}
return s;
}


int main() 
{ 
	FILE *fp;
	char filename[10];
	printf("請輸入文件名(*.txt):");
	scanf("%s",filename);
    if((fp=fopen("a.txt","w"))==NULL)
	{  
		printf("cannot open file\n");
		exit(0);
	}
    
	int maze[M][N];
    int direction[][2]={0,1,1,0,0,-1,-1,0}; 
   for(;;)
   {
   switch (menv_select())
   {
   case 0:
	   printf("結束\n");
	   return 0;

   case 1:
	   Creatmaze(maze);
       mazePath(maze,direction,1,1,6,9);
       break;
   case 2:
      
 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,0,1,
  1,0,1,1,1,0,0,0,0,0,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,
  };
  mazePath(maze,direction,1,1,6,9);

   }
   }
}