用c语言写一个代码:参考课本迷宫问题的求解,用栈求解迷宫问题的所有路径以及最短路径。

以下是一个使用栈来求解迷宫问题的代码，包括所有路径和最短路径：

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

#define MAX_SIZE 100

// 定义迷宫结构体
typedef struct Maze {
    int map[MAX_SIZE][MAX_SIZE]; // 地图
    int row, col; // 地图行数和列数
    int start_row, start_col; // 起点坐标
    int end_row, end_col; // 终点坐标
} Maze;

// 定义栈结构体
typedef struct Stack {
    int row, col; // 栈中元素为迷宫中的坐标
    struct Stack *next; // 指向下一个元素的指针
} Stack;

// 初始化迷宫结构体
void init_maze(Maze *maze) {
    printf("请输入迷宫大小(行 列): ");
    scanf("%d %d", &(maze->row), &(maze->col));
    printf("请输入迷宫地图(0表示可以通过，1表示障碍物):\n");
    for (int i = 0; i < maze->row; i++) {
        for (int j = 0; j < maze->col; j++) {
            scanf("%d", &(maze->map[i][j]));
        }
    }
    printf("请输入起点坐标(行 列): ");
    scanf("%d %d", &(maze->start_row), &(maze->start_col));
    printf("请输入终点坐标(行 列): ");
    scanf("%d %d", &(maze->end_row), &(maze->end_col));
}

// 打印迷宫
void print_maze(Maze maze) {
    printf("迷宫地图:\n");
    for (int i = 0; i < maze.row; i++) {
        for (int j = 0; j < maze.col; j++) {
            printf("%d ", maze.map[i][j]);
        }
        printf("\n");
    }
}

// 初始化栈
void init_stack(Stack **s) {
    *s = NULL;
}

// 判断栈是否为空
bool is_empty(Stack *s) {
    return s == NULL;
}

// 入栈
void push(Stack **s, int row, int col) {
    Stack *node = (Stack*)malloc(sizeof(Stack));
    node->row = row;
    node->col = col;
    node->next = *s;
    *s = node;
}

// 出栈
void pop(Stack **s) {
    if (!is_empty(*s)) {
        Stack *tmp = *s;
        *s = (*s)->next;
        free(tmp);
    }
}

// 获取栈顶元素
void top(Stack *s, int *row, int *col) {
    if (!is_empty(s)) {
        *row = s->row;
        *col = s->col;
    }
}

// 判断当前位置是否可达
bool is_valid(Maze maze, int row, int col, int visited[MAX_SIZE][MAX_SIZE]) {
    if (row < 0 || row >= maze.row || col < 0 || col >= maze.col) {
        return false; // 越界
    }
    if (maze.map[row][col] == 1 || visited[row][col] == 1) {
        return false; // 障碍物或已经访问过
    }
    return true;
}

// 计算两个坐标之间的曼哈顿距离
int manhattan_distance(int row1, int col1, int row2, int col2) {
    return abs(row1 - row2) + abs(col1 - col2);
}

// 计算当前路径的长度
int calculate_path_length(Stack *s) {
    int length = 0;
    while (!is_empty(s)) {
        pop(&s);
        length++;
    }
    return length;
}

// 求解迷宫问题
void solve_maze(Maze maze) {
    Stack *s;
    int visited[MAX_SIZE][MAX_SIZE] = {0}; // 标记数组，记录每个位置是否已经访问过
    int shortest_path_length = MAX_SIZE * MAX_SIZE; // 最短路径的长度
    Stack *shortest_path = NULL; // 最短路径
    init_stack(&s);
    push(&s, maze.start_row, maze.start_col);
    visited[maze.start_row][maze.start_col] = 1;
    while (!is_empty(s)) {
        int row, col;
        top(s, &row, &col);
        if (row == maze.end_row && col == maze.end_col) {
            // 找到一条路径
            int path_length = calculate_path_length(s);
            if (path_length < shortest_path_length) {
                // 更新最短路径
                shortest_path_length = path_length;
                shortest_path = s;
            }
            // 打印当前路径
            printf("找到一条路径: ");
            while (!is_empty(s)) {
                int r, c;
                top(s, &r, &c);
                printf("(%d,%d) ", r, c);
                pop(&s);
            }
            printf("\n");
            continue;
        }
        bool find_next = false;
        for (int i = 0; i < 4; i++) {
            int next_row = row, next_col = col;
            if (i == 0) {
                next_row--;
            } else if (i == 1) {
                next_row++;
            } else if (i == 2) {
                next_col--;
            } else if (i == 3) {
                next_col++;
            }
            if (is_valid(maze, next_row, next_col, visited)) {
                push(&s, next_row, next_col);
                visited[next_row][next_col] = 1;
                find_next = true;
                break;
            }
        }
        if (!find_next) {
            // 没有可达的位置，回溯
            pop(&s);
        }
    }
    if (shortest_path != NULL) {
        // 打印最短路径
        printf("最短路径: ");
        while (!is_empty(shortest_path)) {
            int row, col;
            top(shortest_path, &row, &col);
            printf("(%d,%d) ", row, col);
            pop(&shortest_path);
        }
        printf("\n");
    } else {
        printf("没有找到可行路径\n");
    }
}

int main() {
    Maze maze;
    init_maze(&maze);
    print_maze(maze);
    solve_maze(maze);
    return 0;
}

该代码使用了栈来实现深度优先搜索，找到一条路径后打印路径，并记录最短路径的长度和路径内容。在搜索结束后，打印最短路径。