data_structure_exam：13.迷宫求解问题

迷宫求解

以一个m * n的矩阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

设计要求

实现一个以链表作存储结构的栈类型，编写一个求解迷宫的非递归程序,求得的通路以三元组（i，j，d）的形式输出
i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向
- 例如对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。
编写递归形式的算法，求得迷宫中所有可能的通路
以方阵形式输出迷宫及其通路

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAZE_SIZE 10
// 迷宫的坐标结构
typedef struct {
    int row;
    int col;
} Position;
// 栈节点结构
typedef struct Node {
    Position pos;
    struct Node* next;
} Node;
// 栈结构
typedef struct {
    Node* top;
} Stack;
// 初始化栈
void initStack(Stack* stack) {
    stack->top = NULL;
}
// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == NULL;
}
// 入栈
void push(Stack* stack, Position pos) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->pos = pos;
    newNode->next = stack->top;
    stack->top = newNode;
}
// 出栈
Position pop(Stack* stack) {
    if (!isEmpty(stack)) {
        Position pos = stack->top->pos;
        Node* temp = stack->top;
        stack->top = stack->top->next;
        free(temp);
        return pos;
    }
    else {
        printf("错误：堆栈为空\n");
        exit(EXIT_FAILURE);
    }
}
// 非递归求解迷宫通路
void findPath(int maze[MAZE_SIZE][MAZE_SIZE], Position start, Position end) {
    Stack stack;
    initStack(&stack);
    push(&stack, start);
    maze[start.row][start.col] = -1; // 标记为已访问
    while (!isEmpty(&stack)) {
        Position current = pop(&stack);
        int row = current.row;
        int col = current.col;
        if (current.row == end.row && current.col == end.col) {
            printf("找到出口:\n");
            printf("(%d,%d)\n", current.row, current.col);
            break;
        }
        if (row > 0 && maze[row - 1][col] == 0) { // 上
            push(&stack, (Position) { row - 1, col });
            maze[row - 1][col] = -1;
        }
        if (row < MAZE_SIZE - 1 && maze[row + 1][col] == 0) { // 下
            push(&stack, (Position) { row + 1, col });
            maze[row + 1][col] = -1;
        }
        if (col > 0 && maze[row][col - 1] == 0) { // 左
            push(&stack, (Position) { row, col - 1 });
            maze[row][col - 1] = -1;
        }
        if (col < MAZE_SIZE - 1 && maze[row][col + 1] == 0) { // 右
            push(&stack, (Position) { row, col + 1 });
            maze[row][col + 1] = -1;
        }
    }
    if (isEmpty(&stack)) {
        printf("没有通路。\n");
    }
}
// 打印迷宫及通路
void printMaze(int maze[MAZE_SIZE][MAZE_SIZE]) {
    printf("迷宫:\n");
    for (int i = 0; i < MAZE_SIZE; i++) {
        for (int j = 0; j < MAZE_SIZE; j++) {
            printf("%2d ", maze[i][j]);
        }
        printf("\n");
    }
}
int main() {
    int maze[MAZE_SIZE][MAZE_SIZE] = {
        {1, 0, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
        {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
        {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
        {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
        {1, 0, 0, 0, 1, 0, 0, 0, 1, 1},
        {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
        {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
        {1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
    };
    Position start = { 0, 1 };
    Position end = { 8, 9 };
    printMaze(maze);
    findPath(maze, start, end);
    return 0;
}

 1  0  1  1  1  1  1  1  1  1
 1  0  0  1  0  0  0  1  0  1
 1  0  0  1  0  0  0  1  0  1
 1  0  0  0  0  1  1  0  0  1
 1  0  1  1  1  0  0  0  0  1
 1  0  0  0  1  0  0  0  1  1
 1  0  1  0  0  0  1  0  0  1
 1  0  1  1  1  0  1  1  0  1
 1  1  0  0  0  0  0  0  0  0
 1  1  1  1  1  1  1  1  1  1
找到出口:
(8,9)
结果测试：(0,1,2)，(1,1,2)，(2,1,2)，(3,1,2)，(4,1,2)，(4,2,1)，(4,3,1)，(5,3,2)，(6,3,2)，(7,3,2)，(8,3,2)，(8,4,1)，(8,5,1)，(8,6,1)，(8,7,1)，(8,8,1)，(8,9,2)其中0表示向上，1表示向右，2表示向下，3表示向左。