C语言非递归算法求解迷宫问题

本文介绍使用C语言，通过链表实现栈结构，以非递归的方式求解迷宫问题。程序输入一个 m*n 的迷宫矩阵，其中 0 代表通路，1 代表障碍，输出从入口到出口的路径，路径以三元组 (i, j, d) 的形式表示，其中 (i, j) 表示迷宫中的坐标，d 表示走到下一坐标的方向。

以下是完整的 C 语言代码：

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

// 定义迷宫的大小
#define M 6
#define N 6

// 定义方向常量
#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3

// 定义迷宫的结点
typedef struct Node {
    int i;
    int j;
    int direction;
    struct Node* next;
} Node;

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

// 初始化栈
void initStack(Stack* stack) {
    stack->top = NULL;
}

// 判断栈是否为空
int isEmpty(Stack* stack) {
    return stack->top == NULL;
}

// 入栈
void push(Stack* stack, int i, int j, int direction) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->i = i;
    node->j = j;
    node->direction = direction;
    node->next = stack->top;
    stack->top = node;
}

// 出栈
void pop(Stack* stack) {
    if (isEmpty(stack)) {
        return;
    }
    Node* node = stack->top;
    stack->top = stack->top->next;
    free(node);
}

// 获取栈顶元素
Node* top(Stack* stack) {
    return stack->top;
}

// 判断是否为出口
int isExit(int i, int j) {
    return i == M - 1 && j == N - 1;
}

// 判断是否为通路
int isPath(int maze[M][N], int i, int j) {
    return i >= 0 && i < M && j >= 0 && j < N && maze[i][j] == 0;
}

// 求解迷宫
void solveMaze(int maze[M][N]) {
    Stack stack;
    initStack(&stack);
    push(&stack, 0, 0, RIGHT); // 入口为(0, 0)，方向为右

    while (!isEmpty(&stack)) {
        Node* node = top(&stack);
        int i = node->i;
        int j = node->j;
        int direction = node->direction;

        // 判断是否为出口
        if (isExit(i, j)) {
            printf("(%d, %d, %d)", i, j, direction);
            Node* temp = node->next;
            while (temp != NULL) {
                printf("->(%d, %d, %d)", temp->i, temp->j, temp->direction);
                temp = temp->next;
            }
            printf("\n");
            return;
        }

        // 尝试向下一个方向移动
        switch (direction) {
            case UP:
                i--;
                break;
            case RIGHT:
                j++;
                break;
            case DOWN:
                i++;
                break;
            case LEFT:
                j--;
                break;
        }

        // 判断是否为通路
        if (isPath(maze, i, j)) {
            maze[i][j] = 1; // 标记为已经走过
            push(&stack, i, j, UP); // 先尝试向上走
        } else {
            // 尝试下一个方向
            node->direction++;
            if (node->direction > LEFT) {
                pop(&stack);
            }
        }
    }

    printf("No path found.\n");
}

int main() {
    int maze[M][N] = {
        {0, 1, 0, 0, 0, 0},
        {0, 1, 0, 1, 1, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 1, 1, 1, 0, 1},
        {0, 0, 0, 0, 0, 0},
        {0, 0, 0, 1, 1, 0}
    };

    solveMaze(maze);

    return 0;
}

代码说明

程序首先定义了迷宫的大小、方向常量、迷宫节点和栈的结构体。
实现栈的基本操作：初始化、判空、入栈、出栈、取栈顶元素。
定义了判断是否为出口和通路的函数。
solveMaze 函数是解决迷宫的核心函数，它使用栈来保存当前位置和方向，并通过迭代寻找通路。
主函数中定义了一个示例迷宫，并调用 solveMaze 函数求解迷宫路径。

总结

本文提供了一个 C 语言实现的非递归算法来解决迷宫问题。该程序使用链表实现栈结构，并以三元组的形式输出迷宫路径，方便用户理解迷宫路径的求解过程。