迷宫求解c#代码

解题思路针对本题是一个6*6矩阵的迷宫首先迷宫是一个由0可走和1墙组成的网格外围一圈都是墙。需要从(1,1)走到(4,4)。我们采用广度优先搜索BFS算法因为 BFS 天然保证第一次到达终点时走的步数最少适合求最短路径。主要想法是先从起点出发一圈一圈向外走用一个队列记录所走的位置每次从队列中取出一个元素查看它上下左右的四个邻居如果邻居是0通路且没有被访问过就把其加入队列并且记录它的前驱逐步扩展到终点最后在重点回溯便可找到路径。关键算法1.定义迷宫地图int[,] mg new int[M 2, N 2] { ... };迷宫四周都是墙因此数组实际大小要比原数组大一圈避免数组下标越界2.方向数组int[] dx { -1, 1, 0, 0 }; int[] dy { 0, 0, -1, 1 };分别对应上下左右四个方位的移动变化3.记录前驱和访问状态int[,] prevX new int[M 2, N 2]; int[,] prevY new int[M 2, N 2]; bool[,] visited new bool[M 2, N 2];prevX和prevY用来存储每个格子的前驱坐标。visited防止重复走同一个格子避免死循环。4.队列Queueint queueX new Queueint(); Queueint queueY new Queueint();5.BFS主循环while (queueX.Count 0) { int x queueX.Dequeue(); int y queueY.Dequeue(); if (x endX y endY) break; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (边界合法 mg[nx, ny] 0 !visited[nx, ny]) { visited[nx, ny] true; prevX[nx, ny] x; prevY[nx, ny] y; queueX.Enqueue(nx); queueY.Enqueue(ny); } } }每次取出一个格子如果是终点就停止扩展。检查四个方向的邻居符合条件的就标记为已访问、记录前驱、入队。运行截图代码详情using System; using System.Collections.Generic; using System.Linq; namespace MazeSimple { class Program { static void Main() { const int M 4; const int N 4; const int startX 1, startY 1; const int endX 4, endY 4; int[,] mg new int[M 2, N 2] { {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} }; var directions new (int dx, int dy)[] { (-1, 0), (1, 0), (0, -1), (0, 1) }; int rows M 2; int cols N 2; int[,] prevX new int[rows, cols]; int[,] prevY new int[rows, cols]; bool[,] visited new bool[rows, cols]; for (int i 0; i rows; i) for (int j 0; j cols; j) prevX[i, j] prevY[i, j] -1; var queue new Queue(int x, int y)(); visited[startX, startY] true; queue.Enqueue((startX, startY)); while (queue.Count 0) { var (x, y) queue.Dequeue(); if (x endX y endY) break; foreach (var (dx, dy) in directions) { int nx x dx; int ny y dy; if (nx 0 nx rows ny 0 ny cols mg[nx, ny] 0 !visited[nx, ny]) { visited[nx, ny] true; prevX[nx, ny] x; prevY[nx, ny] y; queue.Enqueue((nx, ny)); } } } if (prevX[endX, endY] -1) { Console.WriteLine(没有找到路径); return; } var path new List(int x, int y)(); int curX endX, curY endY; while (!(curX startX curY startY)) { path.Add((curX, curY)); int px prevX[curX, curY]; int py prevY[curX, curY]; curX px; curY py; } path.Add((startX, startY)); path.Reverse(); Console.WriteLine(迷宫路径从起点到终点); Console.WriteLine(string.Join( → , path.Select(p $({p.x},{p.y})))); PrintMaze(mg, rows, cols); } static void PrintMaze(int[,] mg, int rows, int cols) { Console.WriteLine(\n迷宫地图1墙0路); for (int i 0; i rows; i) { for (int j 0; j cols; j) Console.Write(mg[i, j] ); Console.WriteLine(); } } } }