1.问题描述
已知一个 6×6 的迷宫，可将其视作在一个坐标系中，令起点 (1,1)，终点 (4,4)，墙：1、路：0，要求用队列实现最短路径搜索。
2.算法思路
题目要求使用队列（先进先出）求解最短路径，可以采用广度优先搜索的思想。判断条件为：是否最先到达终点，最终需输出对应的路线。
2.1需要记录的信息
（1）为判断下一步的走向，队列中每个元素要存储当前位置的坐标(x, y)；
（2）为得到具体路径，另外单独使用一个前驱数组prev[x, y]，记录每个格子是的父节点。这样在找到终点后，可以反向追溯出完整路径。
2.2算法步骤
（1）初始：将起点坐标入队，标记起点的前驱为null。
（2）循环处理队列，直到队列为空：
从队列头部取出一个位置，记为current。
①current是终点：停止搜索。
②current不是终点：依次检查current的四个方向（上、下、左、右），计算邻居坐标next,若存在next在迷宫范围内（值为 0）、且没有被访问过（前驱数组中尚无记录），则将next入队，并在prev数组中记录：prev[next.x, next.y] = current。
（3）搜索停止后，如果找到了终点，就从终点开始反复通过prev数组回溯到起点，将经过的坐标收集起来，最后反转顺序，得到从起点到终点的最短路径。
3.关键代码及运行截图
3.1主程序
using System; using System.Collections.Generic; public struct Point { public int X, Y; public Point(int x, int y) { X = x; Y = y; } } public static class MazeSolver { public static List<Point> Solve(int[,] maze, Point start, Point end) { int rows = maze.GetLength(0); int cols = maze.GetLength(1); if (!IsValid(start, rows, cols) || !IsValid(end, rows, cols)) return null; if (maze[start.X, start.Y] == 1 || maze[end.X, end.Y] == 1) return null; // 访问标记 bool[,] visited = new bool[rows, cols]; // 前驱数组 Point?[,] prev = new Point?[rows, cols]; Queue<Point> queue = new Queue<Point>(); queue.Enqueue(start); visited[start.X, start.Y] = true; prev[start.X, start.Y] = null; // 四个方向：上、下、左、右 int[] dx = { -1, 1, 0, 0 }; int[] dy = { 0, 0, -1, 1 }; while (queue.Count > 0) { Point cur = queue.Dequeue(); // 到达终点，开始回溯路径 if (cur.X == end.X && cur.Y == end.Y) { List<Point> path = new List<Point>(); Point? p = end; while (p != null) { path.Add(p.Value); p = prev[p.Value.X, p.Value.Y]; } path.Reverse(); // 反转得到起点到终点的顺序 return path; } // 扩展四个方向 for (int i = 0; i < 4; i++) { int nx = cur.X + dx[i]; int ny = cur.Y + dy[i]; if (IsValid(nx, ny, rows, cols) && maze[nx, ny] == 0 && !visited[nx, ny]) { visited[nx, ny] = true; prev[nx, ny] = cur; queue.Enqueue(new Point(nx, ny)); } } } return null; } private static bool IsValid(Point p, int rows, int cols) => p.X >= 0 && p.X < rows && p.Y >= 0 && p.Y < cols; private static bool IsValid(int x, int y, int rows, int cols) => x >= 0 && x < rows && y >= 0 && y < cols; }3.2测试程序
class Program { static void Main() { // 题目对应6x6迷宫 int[,] maze = new int[6, 6] { {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} }; Point start = new Point(1, 1); Point end = new Point(4, 4); Stopwatch sw = Stopwatch.StartNew(); List<Point> path = MazeSolver.Solve(maze, start, end); sw.Stop(); if (path != null) { Console.WriteLine("最短路径："); foreach (Point p in path) Console.WriteLine($"({p.X}, {p.Y})"); Console.WriteLine($"路径长度：{path.Count}"); } else { Console.WriteLine("没有找到路径"); } Console.WriteLine($"搜索耗时：{sw.Elapsed.TotalMilliseconds} 毫秒"); } }3.3结果截图
4.时间、空间复杂度
针对队列BFS求解迷宫算法，时间复杂度为 O(rows × cols)，空间复杂度为 O(rows × cols)。
5.总结
本次作业使用队列实现了迷宫最短路径的求解。通过将起点入队，逐层扩展邻居节点，并利用prev前驱数组记录每个格子的父节点，最终在第一次到达终点时回溯出完整路径。时间复杂度为 O(rows × cols)，空间复杂度为 O(rows × cols)，对于 6×6 的小规模迷宫，运行耗时在亚毫秒级，效率较高。与栈相比，队列 BFS 需要额外的prev数组存储前驱，但能确保最短路径。通过本次实验，加深了对队列在广度优先搜索中应用的理解，掌握了路径回溯的技巧，也熟悉了 C# 中Stopwatch等工具的使用。
https://gitee.com/dashboard/projectshttps://github.com/Zimoo-o/maze-queue-csharp
