一、项目背景详细介绍

在计算机科学中，“迷宫问题”是一个非常经典的问题模型，几乎贯穿了：

• C 语言

• 数据结构

• 算法设计

• 人工智能（路径规划）

迷宫的本质是：

在一个二维空间中，从起点出发，在障碍约束下，寻找一条到达终点的路径

而“最短路径问题”则进一步提出要求：

在所有可行路径中，找到步数最少的一条

在教学中，该问题具有极高价值：

• 迷宫 → 二维数组建模

• 移动 → 坐标变换

• 最短路径 → BFS 算法

• 回溯路径 → 前驱记录思想

因此，本项目的目标是：

使用 C 语言创建一个迷宫地图，并利用 BFS 算法求解从起点到终点的最短路径，并将路径可视化输出。

---

二、项目需求详细介绍

1️⃣ 迷宫地图需求

• 使用二维数组表示迷宫

• 地图大小：10 × 10

• 包含以下元素：

符号	含义
#	墙（不可通行）
	通路
S	起点
E	终点
*	最短路径

---

2️⃣ 功能需求

系统应实现以下功能：

1. 创建并初始化迷宫

2. 显示原始迷宫

3. 使用 BFS 搜索最短路径

4. 回溯并标记最短路径

5. 输出最终迷宫结果

---

3️⃣ 算法要求

• 使用 广度优先搜索（BFS）

• 不使用递归 DFS 求最短路径

• 使用队列实现 BFS

• 使用“前驱数组”记录路径

---

4️⃣ 技术要求

• 使用二维数组

• 使用结构体

• 使用队列思想（数组实现）

• 使用标准 C 语言

---

三、相关技术详细介绍

1️⃣ 迷宫的二维数组建模

char maze[ROW][COL];

• 行表示 y 坐标

• 列表示 x 坐标

---

2️⃣ 最短路径算法选择：BFS

为什么不用 DFS？

• DFS 找到的是“某一条路径”

• 不能保证最短

BFS 的优势

• 按层搜索

• 第一次到达终点即为最短路径

---

3️⃣ 队列在 BFS 中的作用

BFS 的核心数据结构是 队列（Queue）：

入队 → 扩展 → 出队

保证搜索顺序为“先近后远”。

---

4️⃣ 前驱记录思想（路径回溯）

为了输出完整路径，需要：

• 对每一个格子记录它是从哪里来的

• 到达终点后反向回溯

---

四、实现思路详细介绍

1️⃣ 系统整体流程

1. 初始化迷宫

2. 找到起点 S

3. BFS 搜索终点 E

4. 记录每个节点的前驱

5. 从终点回溯到起点

6. 标记最短路径

7. 输出最终迷宫

---

2️⃣ BFS 搜索流程

起点入队 while 队列非空： 出队 扩展上下左右 合法且未访问 → 入队

---

3️⃣ 路径标记策略

• 起点 S、终点 E 保留

• 中间路径标记为 *

---

五、完整实现代码

#include <stdio.h>

#define ROW 10
#define COL 10

/* ===============================
   迷宫地图
   =============================== */
char maze[ROW][COL] = {
    {'#','#','#','#','#','#','#','#','#','#'},
    {'#','S',' ',' ','#',' ',' ',' ',' ','#'},
    {'#','#','#',' ','#',' ','#','#',' ','#'},
    {'#',' ',' ',' ',' ',' ','#',' ',' ','#'},
    {'#',' ','#','#','#',' ','#',' ','#','#'},
    {'#',' ',' ',' ','#',' ',' ',' ',' ','#'},
    {'#','#','#',' ','#','#','#','#',' ','#'},
    {'#',' ',' ',' ',' ',' ',' ','#',' ','#'},
    {'#',' ','#','#','#','#',' ',' ','E','#'},
    {'#','#','#','#','#','#','#','#','#','#'}
};

/* ===============================
   方向数组（右 下 左 上）
   =============================== */
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

/* ===============================
   位置结构体
   =============================== */
typedef struct {
    int x, y;
} Node;

/* ===============================
   BFS 队列
   =============================== */
Node queue[ROW * COL];
int front = 0, rear = 0;

/* ===============================
   访问标记 & 前驱数组
   =============================== */
int visited[ROW][COL];
Node prev[ROW][COL];

/* ==========================================
   功能：显示迷宫
   ========================================== */
void showMaze()
{
    int i, j;
    for (i = 0; i < ROW; i++)
    {
        for (j = 0; j < COL; j++)
            printf("%c ", maze[i][j]);
        printf("\n");
    }
}

/* ==========================================
   功能：BFS 搜索最短路径
   ========================================== */
void bfs(int sx, int sy)
{
    Node start = {sx, sy};
    queue[rear++] = start;
    visited[sy][sx] = 1;
    prev[sy][sx] = (Node){-1, -1};

    while (front < rear)
    {
        Node cur = queue[front++];

        if (maze[cur.y][cur.x] == 'E')
            return;

        for (int i = 0; i < 4; i++)
        {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            if (nx >= 0 && nx < COL &&
                ny >= 0 && ny < ROW &&
                !visited[ny][nx] &&
                maze[ny][nx] != '#')
            {
                visited[ny][nx] = 1;
                prev[ny][nx] = cur;
                queue[rear++] = (Node){nx, ny};
            }
        }
    }
}

/* ==========================================
   功能：回溯并标记最短路径
   ========================================== */
void markPath(int ex, int ey)
{
    Node cur = {ex, ey};

    while (prev[cur.y][cur.x].x != -1)
    {
        Node p = prev[cur.y][cur.x];
        if (maze[p.y][p.x] == ' ')
            maze[p.y][p.x] = '*';
        cur = p;
    }
}

/* ===============================
   主函数
   =============================== */
int main()
{
    int sx, sy, ex, ey;

    /* 查找起点和终点 */
    for (int i = 0; i < ROW; i++)
        for (int j = 0; j < COL; j++)
        {
            if (maze[i][j] == 'S')
            {
                sx = j;
                sy = i;
            }
            if (maze[i][j] == 'E')
            {
                ex = j;
                ey = i;
            }
        }

    printf("原始迷宫：\n");
    showMaze();

    bfs(sx, sy);
    markPath(ex, ey);

    printf("\n最短路径结果：\n");
    showMaze();

    return 0;
}

六、代码详细解读

1️⃣ bfs

• 使用队列实现广度优先搜索

• 保证第一次到达终点即为最短路径

• 同时记录每个节点的前驱

---

2️⃣ prev 数组

• 保存路径来源

• 为回溯最短路径提供依据

---

3️⃣ markPath

• 从终点反向回溯到起点

• 将路径标记为 *

---

4️⃣ showMaze

• 将迷宫状态可视化输出

---

七、项目详细总结

通过本项目，可以系统掌握：

✅ 二维数组建模复杂问题
✅ BFS 算法解决最短路径
✅ 队列的实际工程用法
✅ 路径回溯思想
✅ 算法与系统设计结合能力

这是一个极其经典、极其重要的 C 语言综合项目，在课程设计与面试中都非常有分量。

---

八、项目常见问题及解答

Q1：为什么 BFS 一定是最短路径？

因为无权图中 BFS 按层扩展。

---

Q2：能用 DFS 吗？

可以找路径，但不保证最短。

---

Q3：迷宫能随机生成吗？

可以，用随机算法生成墙即可。

---

九、扩展方向与性能优化

1️⃣ 随机迷宫生成算法
2️⃣ 使用栈实现 DFS 对比
3️⃣ 增加路径长度统计
4️⃣ 多起点多终点搜索
5️⃣ 升级为 A* 算法