數據結構學習：迷宮問題

[問題描述]
迷宮實驗是取自心理學的一個古典實驗。在該實驗中，把一隻老鼠從一個無頂大盒子的門放入，在盒中設置了許多牆，對行進方向形成了多處阻擋。盒子僅有一個出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達出口。對同一隻老鼠重複進行上述實驗，一直到老鼠從入口到出口，而不走錯一步。老鼠經多次試驗終於得到它學習走通迷宮的路線。設計一個計算機程序對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。

[基本要求]
要求程序輸出：
(1)一條通路的二元組(i，j)數據序列，(i，j)表示通路上某一點的坐標。
(2)用一種標誌(如數字8)在二維數組中標出該條通路，並在屏幕上輸出二維數組。

本算法需要處理的數據主要是當前已走的路徑。經過反覆思考，我決定通過棧來實現。後附代碼中，結構體 Stack 保存了一個順序棧，其中 top 是棧頂元素的索引值，當棧為空時，其值為 -1 ；bottom 為一個指向棧所使用的空間的首地址的指針（棧底指針），當 InitStack 函數初始化一個棧的時候，會實際分配內存空間並使此指針指向分配的空間。此外，還有名為 Coord 的結構體用於保存一個迷宮中的位置和已經嘗試過的方向。在主函數內的死循環中，表示小老鼠的 current 結構體變量每嘗試下一格，都會將自身 push 到棧中保存起來。由於 Coord 結構體亦保存了已嘗試過的方向，回退後能夠緊接著上一次在此位置時的進度繼續向四面八方探索。

//
//  main.c
//  Maze
//
//  Created by 潘岸平 on 2017/10/31.
//  Copyright © 2017年 潘岸平. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

#define LINE_MAX 15
#define COLUMN_MAX 15

typedef uint8_t BOOL;

struct Coord {
    int i;
    int j;
    uint8_t direction;
};

struct Stack {
    struct Coord* bottom;
    int top;
};

void InitStack(struct Stack* stack, int capacity) {
    stack -> top = -1;
    stack -> bottom = (struct Coord*) malloc(capacity * sizeof(struct Coord));
}

void push(struct Stack* stack, struct Coord coord) {
    stack -> bottom[++stack -> top] = coord;
}

struct Coord pop(struct Stack* stack) {
    return stack -> bottom[stack -> top--];
}

BOOL isEmpty(struct Stack* stack) {
    return stack -> top == -1;
}

BOOL valid(struct Coord coord, int maze[][COLUMN_MAX]) {
    if(coord.i < 0 || coord.j < 0 ||
       coord.i >= LINE_MAX || coord.j >= COLUMN_MAX ||
       maze[coord.i][coord.j]) return FALSE;
    return TRUE;
}

void printStack(struct Stack* stack) {
    int index;
    for(index = 0; index <= stack -> top; ++index) {
        printf("(%d, %d)\n", stack -> bottom[index].i, stack -> bottom[index].j);
    }
    printf("(%d, %d)\n", LINE_MAX - 1, COLUMN_MAX - 1);
}

void printMaze(int maze[][COLUMN_MAX]) {
    int i, j;
    for(i = 0; i < LINE_MAX; ++i) {
        for(j = 0; j < COLUMN_MAX; ++j) {
            switch(maze[i][j]) {
                case 0:
                    putchar(' ');
                    break;
                case 1:
                    putchar('@');
                    break;
                case 2:
                    putchar('*');
                    break;
            }
        }
        putchar('\n');
    }
}

int main(int argc, const char * argv[]) {
    int maze[LINE_MAX][COLUMN_MAX] = {
        {0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1},
        {1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1},
        {1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1},
        {0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0},
        {1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0},
        {0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
        {0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1},
        {1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1},
        {0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1},
        {0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1},
        {0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1},
        {1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1},
        {1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1},
        {0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1},
        {1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0}
    }, offset[8][2] = {
        {-1, 0},
        {-1, 1},
        {0, 1},
        {1, 1},
        {1, 0},
        {1, -1},
        {0, -1},
        {-1, -1}
    };
    struct Stack stack;
    struct Coord current, next;
    InitStack(&stack, LINE_MAX * COLUMN_MAX);
    current.i = 0;
    current.j = 0;
    current.direction = 0;
    while(TRUE) {
        maze[current.i][current.j] = 2;
        if(current.direction == 8) {
            if(isEmpty(&stack)) {
                break;
            }
            maze[current.i][current.j] = 0;
            current = pop(&stack);
            continue;
        }
        if(current.i == LINE_MAX - 1 && current.j == COLUMN_MAX - 1) {
            puts("\n找到一條路徑：");
            printStack(&stack);
            printMaze(maze);
            maze[current.i][current.j] = 0;
            current = pop(&stack);
            continue;
        }
        next.direction = 0;
        next.i = current.i + offset[current.direction][0];
        next.j = current.j + offset[current.direction][1];
        ++current.direction;
        if(valid(next, maze)) {
            push(&stack, current);
            current = next;
        }
    }
    return 0;
}