目录

一、题目介绍

二、解题思路

1. BFS 算法与队列的作用

2. 迷宫建模

3. 路径记录与回溯

三、关键代码解析

1. MazeNode 类设计

2. 迷宫与方向定义

3. BFS 主循环

4. 路径回溯与打印

四、运行结果与验证

五、总结

---

一、题目介绍

迷宫求解是数据结构与算法中的经典问题，核心目标是找到从入口到出口的有效路径。队列的 “先进先出” 特性，天然适配 BFS 按层探索的逻辑，能保证找到的第一条路径就是最短路径，因此被广泛应用于迷宫、地图寻路等场景。本次作业我使用队列实现广度优先搜索（BFS）算法，基于 C# 语言完成迷宫路径求解。

二、解题思路

1. BFS 算法与队列的作用

• BFS（广度优先搜索）：是一种按 “层” 遍历节点的算法，它会先探索距离起点最近的所有节点，再逐步向外扩展。

• 队列的角色：作为 BFS 的核心数据结构，队列用于存储待探索的节点。每次从队首取出节点进行探索，将该节点的合法邻接节点加入队尾，保证探索顺序的公平性。

2. 迷宫建模

使用二维数组表示迷宫，规则如下：

• 1 代表墙（不可通行区域）

• 0 代表通路（可通行区域）

• 数组的边界统一设为 1，避免探索时越界。

3. 路径记录与回溯

• 节点设计：定义 MazeNode 类，记录当前坐标 (X,Y) 和前驱节点 Parent，用于后续回溯路径。

• 访问标记：将已探索过的通路标记为墙（1），避免重复探索导致死循环。

• 路径回溯：到达出口后，通过节点的 Parent 属性反向回溯，再用栈反转顺序，得到从入口到出口的完整路径。

三、关键代码解析

1. MazeNode 类设计

public class MazeNode
{
    public int X { get; set; }
    public int Y { get; set; }
    public MazeNode Parent { get; set; }

    public MazeNode(int x, int y, MazeNode parent = null)
    {
        X = x;
        Y = y;
        Parent = parent;
    }
}

• 作用：封装迷宫节点的坐标和前驱节点信息，为路径回溯提供支持。

• 核心：Parent 属性记录了到达当前节点的上一步节点，是回溯路径的关键。

2. 迷宫与方向定义

class Program
{
    static int[,] maze = new int[,]
    {
        {1,1,1,1,1,1},
        {1,0,0,0,1,1},
        {1,0,1,0,0,1},
        {1,0,0,0,1,1},
        {1,1,0,0,0,1},
        {1,1,1,1,1,1}
    };

    static int[,] directions = new int[,]
    {
        {-1, 0}, 
        {1, 0},  
        {0, -1}, 
        {0, 1}   
    };

方向数组：用二维数组统一管理四个探索方向，简化后续循环探索的代码。

3. BFS 主循环

Queue<MazeNode> queue = new Queue<MazeNode>();
queue.Enqueue(start);
maze[start.X, start.Y] = 1;

bool found = false;
MazeNode resultNode = null;

while (queue.Count > 0)
{
    var current = queue.Dequeue();

    if (current.X == end.X && current.Y == end.Y)
    {
        found = true;
        resultNode = current;
        break;
    }

    for (int i = 0; i < 4; i++)
    {
        int newX = current.X + directions[i, 0];
        int newY = current.Y + directions[i, 1];

        if (newX >= 0 && newX < maze.GetLength(0) &&
            newY >= 0 && newY < maze.GetLength(1) &&
            maze[newX, newY] == 0)
        {
            var nextNode = new MazeNode(newX, newY, current);
            queue.Enqueue(nextNode);

            maze[newX, newY] = 1;
        }
    }
}

核心逻辑：

1. 初始化队列，将入口节点入队并标记为已访问。

2. 循环取出队首节点，判断是否到达出口。

3. 依次探索四个方向，将合法的新节点入队并标记访问状态。

4. 路径回溯与打印

 static void PrintPath(MazeNode node)
 {
     Stack<MazeNode> pathStack = new Stack<MazeNode>();
     while (node != null)
     {
         pathStack.Push(node);
         node = node.Parent;
     }

     while (pathStack.Count > 0)
     {
         var p = pathStack.Pop();
         Console.WriteLine($"({p.X},{p.Y})");
     }
 }

逻辑：从出口节点开始，通过 Parent 属性反向遍历路径，存入栈中；再依次出栈，得到正向的路径序列。

四、运行结果与验证

程序运行后，控制台输出如下：

五、总结

本次作业通过队列实现 BFS 算法，完成了迷宫的最短路径求解，核心要点如下：

1. 队列的 “先进先出” 特性是 BFS 实现的关键，保证了路径的最短性。

2. MazeNode 类的设计，为路径回溯提供了数据支持。

3. 访问标记和边界判断，避免了死循环和越界错误。

通过本次作业，我不仅掌握了队列与 BFS 的结合应用，也加深了对数据结构在实际问题中应用的理解。