#include
#include
#define MAXSTACK 100
int stack[MAXSTACK]; /* 堆疊的陣列宣告 */
int top = -1; /* 堆疊的頂端 */
int isStackEmpty() {
if ( top == -1 ) return 1; else return 0;
} int push(int d) {
if ( top >= MAXSTACK ) { /* 是否超過堆疊容量 */
printf("堆疊內容全滿\n"); return 0;
}
else { stack[ top] = d; return 1; }
} int pop() {
if ( isStackEmpty() ) return -1; else return stack[top--]; /* 取出資料 */
}
int main() {
int maze[7][10] = { /* 迷宮陣列,數字0可走, 1不可走 */
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* 迷宮出口 */ 1, 0, 1, 0, 1, 0, 0, 0, 0, 1,
1, 0, 1, 0, 0, 0, 1, 1, 0, 1,
1, 0, 1, 0, 1, 0, 1, 1, 0, 1,
1, 0, 1, 0, 1, 0, 0, 0, 1, 1,
1, 0, 0, 0, 1, 1, 1, 0, 0, 1, /* 迷宮入口 */
1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
int i,j;
int x = 5, y=8; /* 迷宮入口座標 */
push(x); push(y);
while ( (x != 1 || y != 1 ) && (! isStackEmpty()) ) { /* 主迴圈 */
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("數字 1: 牆壁\t數字 2: 走過的路徑\t");
printf("數字 3: 回溯路徑\n");
if (isStackEmpty()) printf("死胡同\n");
else {
printf("堆疊內容(從出口到入口): \n");
while (! isStackEmpty()) {
y=pop(); x=pop();
printf("(%d,%d)\n", x,y); /* 顯示座標值 */
}
}
system("PAUSE"); return 0;
}