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

这篇文章介绍了如何使用C语言实现一个非递归算法来解决迷宫问题。

迷宫问题

迷宫问题是一个经典的计算机科学问题，目标是在给定的迷宫中找到一条从入口到出口的路径。迷宫通常表示为一个二维网格，其中一些单元格代表墙壁，而另一些单元格代表通路。

非递归算法

解决迷宫问题的一种常见方法是使用深度优先搜索（DFS）算法。DFS算法可以递归实现，但也可以使用栈数据结构非递归地实现。

代码实现

以下是C语言实现的非递归算法来解决迷宫问题的代码：

// 包含所需的头文件
#include <stdio.h>
#include <stdlib.h>

// 定义迷宫的最大大小
#define MAX_SIZE 100

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

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

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

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

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

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

// 判断坐标是否在迷宫范围内
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"); // 没有找到通路
}

int main() {
    int m, n;
    printf("设置迷宫大小 (m n): ");
    scanf("%d %d", &m, &n);

    int maze[MAX_SIZE][MAX_SIZE];
    printf("初始化迷宫 ( 0 为路径, 1 为障碍):\n");
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &maze[i][j]);
        }
    }

    printf("通路:\n ");
    solveMaze(maze, m, n); // 解决迷宫问题

    return 0;
}

算法解释

该算法使用栈来存储迷宫中当前路径上的位置。算法从入口位置开始，将其推入栈中。然后，算法进入一个循环，在循环中执行以下步骤：

从栈中弹出一个位置。
检查该位置的四个方向（下、右、上、左）。
如果某个方向上的相邻位置在迷宫范围内，是通路，并且尚未访问过，则将该相邻位置推入栈中，并标记为已访问。
如果当前位置是出口位置，则算法结束。

如果栈为空且未找到出口位置，则迷宫中不存在从入口到出口的路径。

总结

这篇博客文章提供了一个C语言实现的非递归算法，用于解决迷宫问题。代码包含详细的注释，解释了算法的每个步骤，并演示了如何使用栈数据结构来跟踪迷宫中的路径。