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.
");
        exit(1);
    }
    s->data[++s->top] = elem;
}

// 出栈
StackElem pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty.
");
        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, newCol, dir);
                if (newRow == m - 1 && newCol == n - 1) {
                    return; // 找到出口，结束函数
                }

                row = newRow;
                col = newCol;
                dir = 0;
            } else {
                dir++;
            }
        }
    }

    printf("No path found.
");
}

int main() {
    int m, n;
    printf("Enter the size of the maze (m n): ");
    scanf("%d %d", &m, &n);

    int maze[MAX_SIZE][MAX_SIZE];
    printf("Enter the maze (0 for path, 1 for obstacle):\n");
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &maze[i][j]);
        }
    }

    printf("Path: ");
    solveMaze(maze, m, n);

    return 0;
}

算法原理

栈结构：使用栈来存储当前位置和搜索方向。
迷宫遍历：从入口开始，依次尝试四个方向（下、右、上、左）进行探索。
回溯：如果当前位置不可行，则回溯到上一个位置，尝试其他方向。
访问标记：使用二维数组 visited 标记已访问过的位置，避免重复访问。
出口判断：当到达出口时，输出路径并结束搜索。

总结

本文通过代码和详细注释解释了使用C语言实现迷宫求解算法的非递归栈方式。这种方法简单易懂，代码结构清晰，便于理解和调试。

希望本文能够帮助你理解迷宫求解算法的实现原理。