C语言栈和队列实现迷宫最短路径算法

迷宫问题描述

假设有一个 m 行 n 列的迷宫，其中有一个入口和一个出口，入口坐标为 (1,1)，出口坐标为 (m,n)。我们需要找到一条从入口通往出口的最短路径，如果路径不存在，则输出'无法通过'信息。

设计思路

数据结构:
- 使用二维数组 maze[m][n] 表示迷宫，maze[i][j] = 0 表示该位置可通行，maze[i][j] = 1 表示该位置为墙壁。
- 使用结构体 Position 表示迷宫中的位置坐标 (x, y)。
- 使用栈和队列分别存储待探索的位置信息，利用其先进后出和先进先出的特性进行路径搜索。
算法:
- 使用广度优先搜索 (BFS) 算法，从入口开始，逐层向外探索可到达的位置。
- 使用队列存储每一层可到达的位置，并使用访问数组 visited[m][n] 记录已访问过的位置，避免重复访问。
- 当找到出口位置时，搜索结束，返回路径信息。
- 如果遍历完所有可到达的位置仍未找到出口，则迷宫无解。

代码实现

以下是使用 C 语言实现迷宫问题求解的代码示例：

#include <stdio.h>
#include <stdbool.h>

#define MAX_MAZE_SIZE 100

// 定义迷宫的行和列
int m, n;

// 定义迷宫的二维数组
int maze[MAX_MAZE_SIZE][MAX_MAZE_SIZE];

// 定义迷宫位置的结构体
typedef struct {
    int x;
    int y;
} Position;

// 定义栈结构体
typedef struct {
    Position data[MAX_MAZE_SIZE * MAX_MAZE_SIZE];
    int top;
} Stack;

// 定义队列结构体
typedef struct {
    Position data[MAX_MAZE_SIZE * MAX_MAZE_SIZE];
    int front;
    int rear;
} Queue;

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

// 判断栈是否为空
bool isStackEmpty(Stack* stack) {
    return stack->top == -1;
}

// 入栈
void push(Stack* stack, Position pos) {
    stack->data[++stack->top] = pos;
}

// 出栈
Position pop(Stack* stack) {
    return stack->data[stack->top--];
}

// 初始化队列
void initQueue(Queue* queue) {
    queue->front = 0;
    queue->rear = -1;
}

// 判断队列是否为空
bool isQueueEmpty(Queue* queue) {
    return queue->front > queue->rear;
}

// 入队列
void enqueue(Queue* queue, Position pos) {
    queue->data[++queue->rear] = pos;
}

// 出队列
Position dequeue(Queue* queue) {
    return queue->data[queue->front++];
}

// 判断位置是否合法且可通行
bool isValidPosition(Position pos) {
    // 位置超出迷宫范围或者为墙(1)时，返回false
    if (pos.x < 0 || pos.x >= m || pos.y < 0 || pos.y >= n || maze[pos.x][pos.y] == 1) {
        return false;
    }
    return true;
}

// 解决迷宫问题的函数
bool solveMaze() {
    Queue queue;
    initQueue(&queue);

    // 初始化访问数组
    bool visited[MAX_MAZE_SIZE][MAX_MAZE_SIZE] = { false };

    Position entry = { 0, 0 };
    Position exit = { m - 1, n - 1 };

    enqueue(&queue, entry);
    visited[entry.x][entry.y] = true;

    while (!isQueueEmpty(&queue)) {
        Position current = dequeue(&queue);

        // 到达出口，找到路径
        if (current.x == exit.x && current.y == exit.y) {
            return true;
        }

        // 检查相邻的四个方向
        Position neighbors[4] = {
            {current.x + 1, current.y},
            {current.x - 1, current.y},
            {current.x, current.y + 1},
            {current.x, current.y - 1}
        };

        for (int i = 0; i < 4; i++) {
            Position neighbor = neighbors[i];
            if (isValidPosition(neighbor) && !visited[neighbor.x][neighbor.y]) {
                enqueue(&queue, neighbor);
                visited[neighbor.x][neighbor.y] = true;
            }
        }
    }

    // 队列空，无法找到路径
    return false;
}

int main() {
    // 获取迷宫的行和列
    printf('请输入迷宫的行数和列数：');
    scanf('%d %d', &m, &n);

    // 获取迷宫的数据
    printf('请输入迷宫的数据（0表示可通行，1表示有墙）：\n');
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf('%d', &maze[i][j]);
        }
    }

    // 解决迷宫问题
    if (solveMaze()) {
        printf('存在从入口到出口的最短路径！\n');
    } else {
        printf('无法找到从入口到出口的路径！\n');
    }

    return 0;
}

总结

本文介绍了如何使用 C 语言、栈和队列数据结构解决迷宫最短路径问题。通过使用广度优先搜索算法，我们可以有效地找到迷宫的最短路径或判断迷宫无解。代码示例详细展示了算法的实现过程，希望能帮助读者更好地理解和应用迷宫求解算法。