用1表示死路，用0表示通路，使用C语言编写一个简单的用栈求解迷宫问题所有路径及最短路径程序

以下是一个基于栈的简单迷宫问题求解程序，包括所有路径和最短路径的求解：

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

#define MAXROW 5 // 迷宫的行数
#define MAXCOL 5 // 迷宫的列数

// 迷宫地图
int maze[MAXROW][MAXCOL] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0}
};

// 定义坐标结构体
typedef struct {
    int row;
    int col;
} Position;

// 定义栈结构体
typedef struct {
    Position pos;
    int dir;
} Element;

Element stack[MAXROW * MAXCOL]; // 栈的最大容量
int top = -1; // 栈顶指针

// 入栈操作
void push(Position pos, int dir) {
    top++;
    stack[top].pos = pos;
    stack[top].dir = dir;
}

// 出栈操作
void pop() {
    top--;
}

// 判断栈是否为空
bool isEmpty() {
    return top == -1;
}

// 判断当前位置是否为出口位置
bool isExit(Position pos) {
    return pos.row == MAXROW - 1 && pos.col == MAXCOL - 1;
}

// 判断当前位置是否为通路
bool isPath(Position pos) {
    if (pos.row < 0 || pos.row >= MAXROW || pos.col < 0 || pos.col >= MAXCOL) {
        return false;
    }
    return maze[pos.row][pos.col] == 0;
}

// 查找迷宫所有路径
void findAllPaths(Position start) {
    push(start, -1); // 将起点入栈，-1表示无方向可走
    while (!isEmpty()) {
        Element element = stack[top]; // 获取栈顶元素
        Position pos = element.pos;
        int dir = element.dir;
        if (isExit(pos)) { // 到达终点，打印路径
            printf("Path: ");
            for (int i = 0; i <= top; i++) {
                printf("(%d,%d) ", stack[i].pos.row, stack[i].pos.col);
            }
            printf("\n");
            pop(); // 弹出栈顶元素，继续寻找其他路径
            continue;
        }
        if (dir < 3) { // 方向控制变量dir表示当前位置能够继续走到的方向，0表示东，1表示南，2表示西，3表示北，-1表示无方向可走
            Position nextPos;
            switch (dir) {
                case 0: // 向东
                    nextPos.row = pos.row;
                    nextPos.col = pos.col + 1;
                    break;
                case 1: // 向南
                    nextPos.row = pos.row + 1;
                    nextPos.col = pos.col;
                    break;
                case 2: // 向西
                    nextPos.row = pos.row;
                    nextPos.col = pos.col - 1;
                    break;
                case 3: // 向北
                    nextPos.row = pos.row - 1;
                    nextPos.col = pos.col;
                    break;
            }
            if (isPath(nextPos)) { // 下一个位置为通路，入栈
                push(nextPos, -1);
                maze[nextPos.row][nextPos.col] = 1; // 标记为已访问
                element.dir++; // 当前位置的方向控制变量加1
                stack[top] = element; // 更新栈顶元素
                continue;
            }
        }
        pop(); // 当前位置无法继续走，弹出栈顶元素
    }
}

// 查找迷宫最短路径
void findShortestPath(Position start) {
    push(start, -1);
    while (!isEmpty()) {
        Element element = stack[top];
        Position pos = element.pos;
        int dir = element.dir;
        if (isExit(pos)) {
            printf("Shortest Path: ");
            for (int i = 0; i <= top; i++) {
                printf("(%d,%d) ", stack[i].pos.row, stack[i].pos.col);
            }
            printf("\n");
            return;
        }
        if (dir < 3) {
            Position nextPos;
            switch (dir) {
                case 0:
                    nextPos.row = pos.row;
                    nextPos.col = pos.col + 1;
                    break;
                case 1:
                    nextPos.row = pos.row + 1;
                    nextPos.col = pos.col;
                    break;
                case 2:
                    nextPos.row = pos.row;
                    nextPos.col = pos.col - 1;
                    break;
                case 3:
                    nextPos.row = pos.row - 1;
                    nextPos.col = pos.col;
                    break;
            }
            if (isPath(nextPos)) {
                push(nextPos, -1);
                maze[nextPos.row][nextPos.col] = 1;
                element.dir++;
                stack[top] = element;
                continue;
            }
        }
        pop();
    }
}

int main() {
    Position start = {0, 0}; // 起点位置
    findAllPaths(start); // 查找所有路径
    printf("\n");
    findShortestPath(start); // 查找最短路径
    return 0;
}

上述程序中，我们使用了一个栈来保存每个已访问的位置及其能够继续走到的方向，从而实现了迷宫所有路径和最短路径的查找。在程序中，我们使用-1表示无方向可走，0表示向东，1表示向南，2表示向西，3表示向北。当一个位置的方向控制变量为3时，表示已经尝试了所有方向但是都无法继续走下去，此时需要弹出栈顶元素。