26-4-17 数据结构作业：用栈解决迷宫问题

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 ListPoint 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]; QueuePoint queue new QueuePoint(); 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) { ListPoint path new ListPoint(); 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(); ListPoint 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