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

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

迷宫问题

迷宫问题是指在一个由路径和障碍物组成的迷宫中，找到一条从起点到终点的路径。

非递归算法

非递归算法是指不使用递归函数调用来实现算法。在本例中，我们使用栈数据结构来跟踪路径，并使用循环来遍历迷宫。

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;
}

// 判断栈是否为空
int isEmpty(Stack *s) {
    return s->top == -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;
}

// 出栈
StackElem pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty.\n");
        exit(1);
    }
    return s->data[s->top--];
}

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

// 解决迷宫问题的非递归函数
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) {
            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;
            } else {
                dir++;
            }
        }
    }

    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;
}

代码解释

StackElem 结构体表示栈中的一个元素，包括行坐标、列坐标和方向。
Stack 结构体表示栈，包括一个 StackElem 数组和栈顶指针 top。
initStack 函数初始化栈，将 top 设置为 -1。
isEmpty 函数判断栈是否为空，如果 top 等于 -1，则栈为空。
push 函数将一个元素入栈，如果栈已满，则输出错误信息并退出程序。
pop 函数将一个元素出栈，如果栈为空，则输出错误信息并退出程序。
isValid 函数判断坐标是否在迷宫范围内。
solveMaze 函数使用栈来解决迷宫问题。
main 函数读取迷宫大小和数据，然后调用 solveMaze 函数解决迷宫问题。

算法步骤

初始化栈，将入口坐标入栈，并将入口坐标标记为已访问。
当栈不为空时，执行以下步骤：
- 从栈顶取出一个元素。
- 从该元素的当前方向开始，尝试四个方向（下右上左）。
- 如果某个方向可以前进且未被访问过，则将该位置入栈，并将该位置标记为已访问。
- 如果找到出口，则结束函数。
- 如果四个方向都无法前进，则回退到上一个位置，并尝试下一个方向。
如果栈为空且没有找到出口，则说明没有通路。

总结

使用栈数据结构可以有效地解决迷宫问题。该算法易于理解和实现，并且可以有效地找到从入口到出口的路径。