C语言迷宫求解算法 - 非递归实现 - 常规

该代码使用C语言实现了一个非递归算法来解决迷宫问题。算法利用栈来存储探索路径，并通过遍历所有可能的路径来寻找出口。以下是算法的详细流程：

定义迷宫的最大大小为100。
定义栈的结构体，包含行坐标、列坐标和方向。

// 定义栈的结构体
typedef struct {
    int row; // 行坐标
    int col; // 列坐标
    int dir; // 方向
} StackElem;

typedef struct {
    StackElem data[MAX_SIZE]; // 栈的数据数组
    int top; // 栈顶指针
} Stack;

初始化栈，将栈顶指针初始化为-1，表示栈为空。

// 初始化栈
void initStack(Stack *s) {
    s->top = -1; // 栈顶指针初始化为-1，表示栈为空
}

判断栈是否为空，当栈顶指针为-1时，栈为空。

// 判断栈是否为空
int isEmpty(Stack *s) {
    return s->top == -1; // 栈顶指针为-1时，栈为空
}

入栈，如果栈满，则输出提示信息并退出程序。否则，将元素入栈。

// 入栈
void push(Stack *s, StackElem elem) {
    if (s->top == MAX_SIZE - 1) { // 栈满时，无法入栈
        printf("栈满.
");
        exit(1);
    }
    s->data[++s->top] = elem; // 栈顶指针加1，并将元素入栈
}

出栈，如果栈为空，则输出提示信息并退出程序。否则，返回栈顶元素并将栈顶指针减1。

// 出栈
StackElem pop(Stack *s) {
    if (isEmpty(s)) { // 栈空时，无法出栈
        printf("栈空.
");
        exit(1);
    }
    return s->data[s->top--]; // 返回栈顶元素，并将栈顶指针减1
}

判断坐标是否在迷宫范围内，如果行坐标大于等于0且小于m，且列坐标大于等于0且小于n，则坐标在迷宫范围内，返回1，否则返回0。

// 判断坐标是否在迷宫范围内
int isValid(int row, int col, int m, int n) {
    return row >= 0 && row < m && col >= 0 && col < n; // 坐标在迷宫范围内时，返回1，否则返回0
}

解决迷宫问题的非递归函数，定义一个栈，初始化栈。

// 解决迷宫问题的非递归函数
void solveMaze(int maze[][MAX_SIZE], int m, int n) {
    Stack stack; // 定义栈
    initStack(&stack); // 初始化栈

    int visited[MAX_SIZE][MAX_SIZE] = {0}; // 记录已访问的位置
    int directions[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 下右上左四个方向

    StackElem start = {0, 0, 0}; // 入口坐标
    push(&stack, start); // 入栈
    visited[0][0] = 1; // 标记入口位置已访问

    while (!isEmpty(&stack)) { // 栈不为空时，循环执行
        StackElem curr = pop(&stack); // 出栈，获取当前位置信息
        int row = curr.row; // 当前行坐标
        int col = curr.col; // 当前列坐标
        int dir = curr.dir; // 当前方向

        while (dir < 4) { // 当前方向小于4时，循环执行
            int newRow = row + directions[dir][0]; // 计算下一个位置的行坐标
            int newCol = col + directions[dir][1]; // 计算下一个位置的列坐标

            if (isValid(newRow, newCol, m, n) && maze[newRow][newCol] == 0 && !visited[newRow][newCol]) {
                // 下一个位置在迷宫范围内，且为通路，且未访问过
                StackElem next = {newRow, newCol, 0}; // 创建下一个位置的信息
                push(&stack, next); // 入栈
                visited[newRow][newCol] = 1; // 标记下一个位置已访问

                printf("('d, 'd, 'd) ", newRow+1, newCol+1, dir+1); // 输出当前位置信息
                if (newRow == m - 1 && newCol == n - 1) {
                    return; // 找到出口，结束函数
                }

                row = newRow; // 更新当前位置的行坐标
                col = newCol; // 更新当前位置的列坐标
                dir = 0; // 重置方向为0
            } else {
                dir++; // 方向加1
            }
        }
    }

    printf("没有通路\n"); // 没有找到通路
}

初始化一个二维数组visited，用于记录已访问的位置。初始化为0。
定义四个方向：下、右、上、左。
定义入口坐标，并将其入栈，标记入口位置已访问。
当栈不为空时，循环执行以下步骤：

出栈，获取当前位置信息。
获取当前位置的行坐标、列坐标和方向。
当前方向小于4时，循环执行以下步骤：
- 计算下一个位置的行坐标和列坐标。
- 如果下一个位置在迷宫范围内，且为通路，且未访问过，则将下一个位置入栈，标记下一个位置已访问，并输出当前位置信息。
- 如果下一个位置是出口，则结束函数。
- 更新当前位置的行坐标、列坐标和方向。

输出"没有通路"。
主函数：

输入迷宫的大小m和n。
初始化迷宫，将路径和障碍输入迷宫数组。
解决迷宫问题，输出通路。

返回0。

该代码是一个基本的迷宫求解算法，可以作为学习非递归算法和栈数据结构的参考。实际应用中，可以通过优化代码提高效率，例如使用更有效率的搜索策略，或使用更复杂的数据结构来存储迷宫信息。