问题定义

迷宫求解问题：给定一个迷宫MAZE[n][m]，入口(x0,y0)和出口(xn,yn)，其中迷宫数组中数字为1的位置代表是墙，数字为0的位置代表是路，要求从入口开始寻找路线直到出口，最终找到的路径标为2。

算法思想

计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续 往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止，如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在 从起点到终点的通道。

根据前面的想法，我们可以直到求解迷宫问题可以遵循以下几个原则。

• 我们需要维护一个栈，一直保存我们探索的路径。

• 从入口进，开始按照东西南北的顺序依次查看是否为1（墙），如果查看到不是墙的则往那个方向走，并且将这个位置入栈。

• 中间会遇到被墙围堵的情况，即三个方向都是1、一个方向为2（已访问），这时候代表这条路走不通，就需要我们将这个位置设为1（假装这是墙，不能再进），然后出栈，并且返回到上一条路径之中。

• 如果最终到达了预定的出口，则成功；如果没有路能到达设定的出口，则程序会不断地将所有路设为墙，说明这个迷宫无法通过。

算法具体流程如下：

1. 初始化一个链表栈，节点保存位置xy和下一个节点的指针next，栈中保存当前栈顶的节点top、栈底的节点bottom和栈大小size（注意在我的实现中，我将链表尾部作为栈顶，链表头部作为栈底，方便打印路径）。然后将迷宫入口位置作为头节点入栈。
2. 开始一个while循环，将栈顶位置设置为2。
   • 如果当前栈顶位置是出口，则打印路径退出。
   • 如果当前栈顶位置不是出口，则从按照东西南北的顺序查看是否迷宫位置为0。
     • 如果找到一个位置为0，则将这个位置压入栈顶并进入下一轮循环。
     • 如果没有找到位置为0，则将当前位置设为1，然后出栈并进入下一轮循环。
   • 如果当前栈的大小为0，代表入口都被出栈了，则找不到路。
3. 按照路径更新原始迷宫打印。（可选）

显然利用回溯法（穷举）只能找到路径，但却无法辨别是否是最短路径。

代码实现

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

// 定义方向
#define East MAZE[x][y+1]
#define West MAZE[x][y-1]
#define South MAZE[x+1][y]
#define North MAZE[x-1][y]
// 定义入口
#define Entrance MAZE[1][1]
// 定义出口
#define Exit MAZE[8][10]

// 定义迷宫
int MAZE[10][12] = { 1,1,1,1,1,1,1,1,1,1,1,1,
                     1,0,0,0,1,1,1,1,1,1,1,1,
                     1,1,1,0,1,1,0,0,0,0,1,1,
                     1,1,1,0,1,1,0,1,1,0,1,1,
                     1,1,1,0,0,0,0,1,1,0,1,1,
                     1,0,0,0,1,1,0,1,1,0,1,1,
                     1,1,1,0,1,1,0,0,1,0,1,1,
                     1,0,1,0,1,1,0,1,1,0,1,1,
                     1,0,0,0,0,0,0,0,1,0,0,1,
                     1,1,1,1,1,1,1,1,1,1,1,1
};

// 定义节点
typedef struct Node {
    int x;
    int y;
    struct Node* next;
} Node;

// 定义栈
typedef struct Stack {
    Node* top;
    Node* bottom;
    int size;
} Stack;

// 入栈
void StackPush(Stack* stack, Node* node) {
    stack->top->next = node;
    stack->top = node;
    stack->size++;
    return;
}

// 出栈
Node* StackPop(Stack* stack) {
    if (stack->size == 0) {
        return NULL;
    }
    Node* p = stack->bottom;
    if (p == stack->top) {
        stack->top = NULL;
    }
    else {
        while (p->next != stack->top) {
            p = p->next;
        }
    }
    Node* poppedNode = stack->top;
    stack->top = p;
    p->next = NULL;
    stack->size--;

    return poppedNode;
}

// 打印路径
void MazePathPrintf(Node* head) {
    printf("找到路径为：\n");
    Node* p = head;
    while (p != NULL) {
        printf("(%d, %d)->", p->x, p->y);
        p = p->next;
    }
    printf("\n");
}

int MazePath(Stack* stack, int** MAZE) {
    // 初始入口
    Node* p = (Node*)malloc(sizeof(Node));
    if (p == NULL) {
        printf("内存分配失败\n");
        return 0;
    }
    p->x = 1;
    p->y = 1;
    p->next = NULL;
    stack->top = p;
    stack->bottom = p;
    stack->size = 1;

    // 回溯法寻找出口
    while (stack->top != NULL) {
        // 定义当前位置
        Node* current = stack->top;
        int x = current->x;
        int y = current->y;
        MAZE[x][y] = 2; // 标记为已访问

        // 如果当前位置是出口
        if (x == 8 && y == 10) {
            MazePathPrintf(stack->bottom);
            return 1;
        }

        // 如果当前位置不是出口，往四个方向找路
        int moved = 0;
        if (East == 0) {
            Node* newNode = (Node*)malloc(sizeof(Node));
            if (newNode == NULL) {
                printf("内存分配失败\n");
                return 0;
            }
            newNode->x = x;
            newNode->y = y + 1;
            newNode->next = NULL;
            StackPush(stack, newNode);
            moved = 1;
        }
        else if (West == 0) {
            Node* newNode = (Node*)malloc(sizeof(Node));
            if (newNode == NULL) {
                printf("内存分配失败\n");
                return 0;
            }
            newNode->x = x;
            newNode->y = y - 1;
            newNode->next = NULL;
            StackPush(stack, newNode);
            moved = 1;
        }
        else if (South == 0) {
            Node* newNode = (Node*)malloc(sizeof(Node));
            if (newNode == NULL) {
                printf("内存分配失败\n");
                return 0;
            }
            newNode->x = x + 1;
            newNode->y = y;
            newNode->next = NULL;
            StackPush(stack, newNode);
            moved = 1;
        }
        else if (North == 0) {
            Node* newNode = (Node*)malloc(sizeof(Node));
            if (newNode == NULL) {
                printf("内存分配失败\n");
                return 0;
            }
            newNode->x = x - 1;
            newNode->y = y;
            newNode->next = NULL;
            StackPush(stack, newNode);
            moved = 1;
        }

        if (!moved) {
            // 如果无路可走则把当前位置设为死路1并出栈
            MAZE[x][y] = 1;
            Node* popped = StackPop(stack);
            if (popped != NULL) {
                free(popped);
            }
        }

        // 如果栈为空表示找不到路了
        if (stack->size == 0) {
            printf("找不到路\n");
            return 0;
        }
    }
}

int main() {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    if (stack == NULL) {
        printf("内存分配失败\n");
        return -1;
    }
    stack->top = NULL;
    stack->bottom = NULL;
    stack->size = 0;

    // 打印原始迷宫
    printf("迷宫为：\n");
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 12; j++) {
            printf("%d ", MAZE[i][j]);
        }
        printf("\n");
    }

    // 创建一个迷宫副本
    int** MAZE_COPY = (int**)malloc(sizeof(int*) * 10);
    if (MAZE_COPY == NULL) {
        printf("内存分配失败\n");
        free(stack);
        return -1;
    }
    for (int i = 0; i < 10; i++) {
        MAZE_COPY[i] = (int*)malloc(sizeof(int) * 12);
        if (MAZE_COPY[i] == NULL) {
            printf("内存分配失败\n");
            for (int k = 0; k < i; k++) {
                free(MAZE_COPY[k]);
            }
            free(MAZE_COPY);
            free(stack);
            return -1;
        }
        for (int j = 0; j < 12; j++) {
            MAZE_COPY[i][j] = MAZE[i][j];
        }
    }

    // 寻找路径
    int flag = MazePath(stack, MAZE_COPY);

    // 把原始迷宫的路径改为2
    Node* current = stack->bottom;
    while (current != NULL) {
        MAZE[current->x][current->y] = 2;
        current = current->next;
    }

    // 打印找到路径后的迷宫
    if (flag) {
        printf("找到路径后的迷宫为：\n");
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 12; j++) {
                printf("%d ", MAZE[i][j]);
            }
            printf("\n");
        }
    }

    // 释放内存
    for (int i = 0; i < 10; i++) {
        free(MAZE_COPY[i]);
    }
    free(MAZE_COPY);

    // 释放栈内存
    while (stack->size > 0) {
        Node* node = StackPop(stack);
        if (node != NULL) {
            free(node);
        }
    }
    free(stack);

    return 0;
}

输出内容为

迷宫为：
1 1 1 1 1 1 1 1 1 1 1 1 
1 0 0 0 1 1 1 1 1 1 1 1 
1 1 1 0 1 1 0 0 0 0 1 1 
1 1 1 0 1 1 0 1 1 0 1 1 
1 1 1 0 0 0 0 1 1 0 1 1 
1 0 0 0 1 1 0 1 1 0 1 1 
1 1 1 0 1 1 0 0 1 0 1 1 
1 0 1 0 1 1 0 1 1 0 1 1 
1 0 0 0 0 0 0 0 1 0 0 1 
1 1 1 1 1 1 1 1 1 1 1 1 
找到路径为：
(1, 1)->(1, 2)->(1, 3)->(2, 3)->(3, 3)->(4, 3)->(4, 4)->(4, 5)->(4, 6)->(3, 6)->(2, 6)->(2, 7)->(2, 8)->(2, 9)->(3, 9)->(4, 9)->(5, 9)->(6, 9)->(7, 9)->(8, 9)->(8, 10)->
找到路径后的迷宫为：
1 1 1 1 1 1 1 1 1 1 1 1 
1 2 2 2 1 1 1 1 1 1 1 1 
1 1 1 2 1 1 2 2 2 2 1 1 
1 1 1 2 1 1 2 1 1 2 1 1 
1 1 1 2 2 2 2 1 1 2 1 1 
1 0 0 0 1 1 0 1 1 2 1 1 
1 1 1 0 1 1 0 0 1 2 1 1 
1 0 1 0 1 1 0 1 1 2 1 1 
1 0 0 0 0 0 0 0 1 2 2 1 
1 1 1 1 1 1 1 1 1 1 1 1