Ch5-4-1e.c

#include< stdio.h>
#include< stdlib.h>
/* 堆疊節點的宣告 */
struct Node
{
int data; /* 儲存堆疊資料 */
struct Node *next; /* 指向下一節點 */
};

typedef struct Node SNode; /* 堆疊節點的新型態 */
typedef SNode *LStack; /* 串列堆疊的新型態 */
LStack top = NULL; /* 堆疊頂端的指標 */

/* 函數: isStackEmpty() 檢查堆疊是否是空的 */
int isStackEmpty()
{
if ( top == NULL )
return 1;
else
return 0;
}

/* 函數: push() 將資料存入堆疊 */
void push(int d)
{
LStack new_node; /* 新節點指標 */
/* 配置節點記憶體 */
new_node = (LStack)malloc(sizeof(SNode));
new_node->data = d; /* 建立節點內容 */
new_node->next = top; /* 新節點指向原開始 */
top = new_node; /* 新節點成為堆疊開始 */
}

/* 函數: pop() 從堆疊取出資料 */
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()
{
/* 迷宮陣列, 數字 0 可走, 1 不可走 */
int maze[7][10] = {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 1, 0, 0, 0, 0, 1,
1, 0, 1, 1, 0, 0, 1, 1, 0, 1,
1, 0, 0, 0, 1, 1, 1, 0, 0, 1,
1, 0, 1, 0, 1, 0, 0, 0, 1, 1,
1, 0, 1, 0, 0, 0, 1, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
int i, j;
int x = 5; /* 迷宮入口座標 */
int y = 8;
maze[5][8] = 7; /* 標示迷宮入口位置 */

printf("\n　迷宮路徑圖(請從右下角(７)走到左上角)\n");
printf("\n數字 0：尚未走過的路徑\t數字 1：牆壁\n");
printf("數字 7：迷宮起始點\n");
for ( i = 0; i <= 6; i++)
{ /* 顯示迷宮圖形 */
for ( j = 0; j <= 9; j++)
printf("%d ", maze[i][j]); /* 顯示座標值 */
printf("\n");
}
printf("\n 想好了嗎？\n");
system("PAUSE");
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] = 9; /* 標示最後位置 */
printf("\n　迷宮完成圖(從右下角走出左上角(９))\n");
for ( i = 0; i <= 6; i++)
{ /* 顯示迷宮圖形 */
for ( j = 0; j <= 9; j++)
printf("%d ", maze[i][j]); /* 顯示座標值 */
printf("\n");
}
printf("\n數字 0：尚未走過的路徑\t數字 1：牆壁\n");
printf("數字 2：走過的路徑\t數字 3：回溯路徑\n");
printf("\n　哇!終於走出來囉\n");
system("PAUSE");
return 0;
}