作業十五：迷宮換路徑

/* 程式範例: Ch5-4-1.c */
#include <stdio.h>
#include <stdlib.h>

struct Node {                  /* 堆疊節點的宣告 */
   int data;                   /* 儲存堆疊資料 */
   struct Node *next;          /* 指向下一節點 */
};
typedef struct Node SNode;    /* 堆疊節點的新型態 */
typedef SNode *LStack;        /* 串列堆疊的新型態 */
LStack top = NULL;             /* 堆疊頂端的指標 */
/* 函數: 檢查堆疊是否是空的 */
int isStackEmpty() {
   if ( top == NULL ) return 1;
   else               return 0;
}
/* 函數: 將資料存入堆疊 */
void push(int d) {
   LStack new_node;            /* 新節點指標 */
   /* 配置節點記憶體 */
   new_node = (LStack)malloc(sizeof(SNode));
   new_node->data = d;         /* 建立節點內容 */
   new_node->next = top;       /* 新節點指向原開始 */
   top = new_node;            /* 新節點成為堆疊開始 */  
}
/* 函數: 從堆疊取出資料 */
int pop() {
   LStack ptr;                 /* 指向堆疊頂端 */
   int temp;
   if ( !isStackEmpty()  ) {  /* 堆疊是否是空的 */
      ptr = top;              /* 指向堆疊頂端 */
      top = top->next;         /* 堆疊指標指向下節點 */
      temp = ptr->data;        /* 取出資料 */
      free(ptr);               /* 釋回節點記憶體 */
      return temp;             /* 堆疊取出 */
   }
   else return -1;
}
/* 主程式: 使用回溯方法在陣列走迷宮 */
int main() {
   int maze[7][10] = { /* 迷宮陣列,數字0可走, 1不可走 */
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 0, 1, 1, 0, 0, 1, 0, 0, 1,
            1, 0, 0, 0, 1, 0, 1, 0, 0, 1,
            1, 1, 1, 0, 1, 0, 1, 0, 0, 1,
            1, 0, 1, 0, 0, 0, 0, 0, 0, 1,
            1, 0, 0, 0, 1, 1, 1, 1, 0, 1,
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
   int i,j;
   int x = 5;                     /* 迷宮入口座標 */
   int y = 8;
   while ( x != 1 || y != 1 ) {   /* 主迴圈 */
      maze[x][y] = 2;             /* 標示為已走過的路 */
      if ( maze[x-1][y] <= 0 ) {  /* 往上方走 */
         x = x - 1;               /* 座標x減1 */
         push(x);                /* 存入路徑 */
         push(y);
      }
      else if ( maze[x+1][y] <= 0 ) { /* 往下方走 */
           x = x + 1;            /* 座標x加1 */
           push(x);             /* 存入路徑 */
           push(y);
         }
         else if ( maze[x][y-1] <= 0 ) { /* 往左方走 */
              y = y - 1;            /* 座標y減1 */
              push(x);             /* 存入路徑 */
              push(y);
           }
           else if ( maze[x][y+1] <= 0 ) {  /* 往右方走 */
                y = y + 1;            /* 座標y加1 */
                push(x);               /* 存入路徑 */
                push(y);
             }
             else {  /* 沒有路可走:迴溯 */
                  maze[x][y] = 3;  /* 表示是迴溯的路 */
                  y = pop();        /* 退回一步 */
                  x = pop();
               }
   }
   maze[x][y] = 2;                /* 標示最後位置 */
   printf("迷宮路徑圖(從右下角到左上角): \n");
   for ( i = 0; i <= 6; i++) {    /* 顯示迷宮圖形 */
      for ( j = 0; j <= 9; j++)
         printf("%d ", maze[i][j]); /* 顯示座標值 */
      printf("\n");
   }
   printf("\n數字 1: 牆壁\n數字 2: 走過的路徑\n");
   printf("數字 3: 回溯路徑\n");
   system("PAUSE");
   return 0;
}