首页 > 代码库 > 迷宫问题
迷宫问题
今天看到个很经典的迷宫问题，这个太经典了 非常适合研究算法方面。
迷宫无非就是一个地图然后找出走出迷宫的线路，经典的递归问题。
废话不多说直接看吧！
1.经典迷宫
2.复杂迷宫问题
3.最优路线迷宫问题
1.经典迷宫
先看地图
从图上标出的起点到终点找出线路的算法
先看地图，地图无非就是一个二维的数组，用某个标记标记为墙壁（这里用数字9）某个标记标记成线路（这里用数字1）其他直接是空白
看看上面迷宫就知道这个二维数组是什么样的了吧
class Program { static int[][] map = new int[9][];static void Main(string[] args) { map[0] = new int[] { 9, 9, 9, 9, 9, 9, 9, 9, 9 }; map[1] = new int[] { 9, 0, 0, 0, 0, 0, 0, 0, 9 }; map[2] = new int[] { 9, 0, 9, 9, 0, 9, 9, 0, 9 }; map[3] = new int[] { 9, 0, 9, 0, 0, 9, 0, 0, 9 }; map[4] = new int[] { 9, 0, 9, 0, 9, 0, 9, 0, 9 }; map[5] = new int[] { 9, 0, 0, 0, 0, 0, 9, 0, 9 }; map[6] = new int[] { 9, 9, 0, 9, 9, 0, 9, 9, 9 }; map[7] = new int[] { 9, 0, 0, 0, 0, 0, 0, 0, 9 }; map[8] = new int[] { 9, 9, 9, 9, 9, 9, 9, 9, 9 }; Console.WriteLine("迷宫地图："); for (int i = 0; i < map.Length; i++) { for (int j = 0; j < map.Length; j++) if (map[i][j] == 9) Console.Write("██"); else Console.Write(" "); Console.WriteLine(""); } System.Console.ReadKey(); }}
然后确定起始点和结束点就可以用递归去计算并输出线路了：
1 static int startX = 1, startY = 1; 2 static int endX = 7, endY = 7; 3 4 static void Go(int i, int j) { 5 int m, n; 6 map[i][j] = 1; 7 if (i == endY && j == endX) { 8 Console.WriteLine("\n迷宫行走路线"); 9 for (m = 0; m < map.Length; m++) {10 for (n = 0; n < map.Length; n++)11 if (map[m][n] == 9)12 Console.Write("██");13 else if (map[m][n] == 1) {14 Console.Write("◇");15 }16 else17 Console.Write(" ");18 Console.WriteLine("");19 }20 }21 if (map[i][j + 1] == 0)22 Go(i, j + 1);23 if (map[i + 1][j] == 0)24 Go(i + 1, j);25 if (map[i][j - 1] == 0)26 Go(i, j - 1);27 if (map[i - 1][j] == 0)28 Go(i - 1, j);29 map[i][j] = 0;30 }
当到达结束点的时候就输出线路，这个应该好理解，后面的逐个方向去递归求解看看也就会了。
2.复杂迷宫问题
先看地图
然后看解法运行结果：
这是一个20*20的迷宫跟上面一样用9标记成墙壁
先打印地图：
class Program { static int[][] map; static void Main(string[] args) { map = new int[20][] { new int[] { 9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9}, new int[] { 9,0,0,0,9,0,0,9,9,9,9,9,9,9,9,9,9,9,9,9}, new int[] { 9,0,9,0,0,0,0,9,9,9,9,9,9,9,9,9,9,9,9,9}, new int[] { 9,0,9,9,9,9,0,0,0,0,0,9,9,9,9,9,9,9,9,9}, new int[] { 9,0,9,9,0,0,0,9,0,9,0,9,9,9,9,9,9,9,9,9}, new int[] { 9,0,0,0,0,9,9,9,0,9,0,0,0,0,9,9,9,9,9,9}, new int[] { 9,9,0,9,9,9,9,9,0,9,9,9,9,0,0,0,9,9,9,9}, new int[] { 9,9,0,9,9,9,9,9,9,9,9,9,9,0,9,9,9,9,9,9}, new int[] { 9,9,0,9,9,9,9,9,9,9,0,0,0,0,9,9,9,9,9,9}, new int[] { 9,0,0,9,9,9,9,9,9,9,0,9,9,9,9,9,9,9,9,9}, new int[] { 9,0,9,9,9,9,9,9,9,9,0,9,9,9,0,9,9,9,9,9}, new int[] { 9,0,9,9,9,9,9,9,9,9,0,0,0,0,9,9,9,9,9,9}, new int[] { 9,0,9,9,9,9,9,9,9,9,9,9,0,9,9,9,9,9,9,9}, new int[] { 9,0,0,9,9,9,9,9,9,9,9,9,0,9,9,9,9,9,9,9}, new int[] { 9,9,0,9,9,0,0,0,0,0,0,0,0,9,9,9,9,9,9,9}, new int[] { 9,9,0,9,9,0,9,9,9,9,9,9,0,9,9,9,9,9,9,9}, new int[] { 9,9,0,9,9,0,9,9,9,9,9,9,0,9,9,9,9,9,9,9}, new int[] { 9,9,0,9,9,0,9,9,9,9,9,9,0,9,9,9,9,9,9,9}, new int[] { 9,9,0,0,0,0,0,0,0,9,9,9,0,0,0,0,0,0,0,9}, new int[] { 9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9} }; Console.ForegroundColor = ConsoleColor.White; Console.WriteLine("迷宫地图："); Console.ForegroundColor = ConsoleColor.Green; for (int i = 0; i < map.Length; i++) { for (int j = 0; j < map.Length; j++) { if (map[i][j] == 9) Console.Write("■"); else Console.Write(" "); } Console.WriteLine(" "); } System.Console.ReadKey(); }}
这里能走的线路比较多所以每条正确线路都用一个结果集进行保存，方便后面求出最短线路
static int startX = 1, startY = 1;//起点 static int endX = 18, endY = 18;//终点 static List<List<string>> list = new List<List<string>>(); static List<string> lis = new List<string>(); static void go(int i, int j) { int m, n; map[i][j] = 1; if (i == endY && j == endX) { Console.ForegroundColor = ConsoleColor.White; Console.WriteLine("\n迷宫行走路线{0}", list.Count); lis.Clear(); for (m = 0; m < map.Length; m++) { for (n = 0; n < map.Length; n++) if (map[m][n] == 9) { Console.ForegroundColor = ConsoleColor.DarkRed; Console.Write("■"); } else if (map[m][n] == 1) { Console.ForegroundColor = ConsoleColor.Yellow; lis.Add("" + m + "," + n); Console.BackgroundColor = ConsoleColor.Blue; Console.Write("{0}", lis.Count.ToString().PadLeft(2, ‘ ‘)); Console.BackgroundColor = ConsoleColor.Black; } else { Console.ForegroundColor = ConsoleColor.Yellow; Console.Write("->"); Console.ForegroundColor = ConsoleColor.Black; } Console.WriteLine(""); } list.Add((lis.ToArray().Clone() as string[]).ToList<string>()); Console.ReadKey(); } if (map[i][j + 1] == 0) go(i, j + 1); //下 if (map[i + 1][j] == 0) //左 go(i + 1, j); if (map[i][j - 1] == 0) //上 go(i, j - 1); if (map[i - 1][j] == 0) //右 go(i - 1, j); map[i][j] = 0; }
走完之后直接在结果集中就可以找出最优线路了：
Console.ForegroundColor = ConsoleColor.White; Console.WriteLine("\n最优路线："); list.OrderBy(a => a.Count).First().ForEach(b =>Console.Write("["+b.ToString() +"]"+ " ")); System.Console.ReadKey();
3.最优路线迷宫问题
前面两种迷宫都还是比较简单的，一看就明白了。下面看看更大更复杂的迷宫进行最优线路选择问题：
一看就头好晕啊，这么烦的东西肯定是用EXCEL这些工具帮忙画出来的然后结合成代码复制黏贴一下的啦。
1 class Program { 2 static int[][] map; 3 static void Main(string[] args) { 4 map = new int[40][] { 5 new int[] { 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, }, 6 new int[] { 9, 0, 9, 0, 0, 0, 9, 0, 0, 0, 0, 0, 9, 9, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 9, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 9, }, 7 new int[] { 9, 0, 9, 0, 9, 0, 9, 0, 9, 9, 9, 0, 9, 9, 0, 9, 9, 9, 9, 0, 9, 0, 9, 9, 0, 9, 0, 9, 9, 0, 9, 0, 9, 9, 9, 9, 0, 9, 9, 9, }, 8 new int[] { 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 0, 9, 0, 9, 9, 0, 9, 0, 9, 0, 9, 9, 0, 9, 0, 9, 9, 0, 9, 0, 9, 9, 9, 9, 0, 9, 9, 9, }, 9 new int[] { 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 9, 0, 9, 0, 0, 0, 0, 9, 0, 9, 9, 0, 9, 0, 0, 0, 0, 9, 0, 9, 9, 9, 9, 0, 9, 9, 9, },10 new int[] { 9, 0, 9, 0, 9, 0, 9, 0, 0, 0, 9, 0, 9, 9, 0, 9, 9, 0, 9, 9, 9, 0, 0, 9, 0, 9, 0, 9, 9, 0, 9, 0, 0, 0, 0, 0, 0, 9, 9, 9, },11 new int[] { 9, 0, 9, 0, 9, 0, 9, 9, 9, 0, 9, 0, 9, 0, 0, 9, 9, 0, 9, 9, 9, 9, 0, 9, 0, 0, 0, 9, 9, 0, 9, 0, 9, 9, 9, 9, 0, 9, 9, 9, },12 new int[] { 9, 0, 9, 0, 9, 0, 9, 9, 9, 0, 9, 0, 9, 9, 0, 9, 0, 0, 0, 0, 0, 9, 0, 9, 9, 9, 9, 9, 9, 0, 9, 0, 9, 9, 9, 9, 0, 9, 9, 9, },13 new int[] { 9, 0, 9, 0, 9, 0, 0, 0, 0, 0, 9, 0, 9, 9, 0, 9, 0, 9, 9, 9, 0, 9, 0, 9, 9, 9, 9, 9, 9, 0, 9, 0, 9, 9, 9, 9, 0, 9, 9, 9, },14 new int[] { 9, 0, 9, 0, 9, 9, 0, 9, 9, 9, 9, 0, 9, 9, 0, 9, 0, 9, 9, 9, 0, 9, 0, 9, 9, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 9, },15 new int[] { 9, 0, 9, 0, 9, 9, 0, 9, 9, 0, 9, 0, 9, 9, 0, 9, 0, 9, 0, 0, 0, 9, 0, 9, 9, 0, 9, 9, 9, 9, 9, 0, 9, 0, 9, 9, 9, 9, 0, 9, },16 new int[] { 9, 0, 9, 0, 9, 9, 0, 0, 9, 0, 0, 0, 9, 9, 0, 9, 0, 9, 0, 9, 9, 9, 0, 0, 9, 0, 9, 0, 0, 0, 0, 0, 9, 0, 9, 0, 0, 0, 0, 9, },17 new int[] { 9, 0, 9, 0, 9, 9, 9, 0, 9, 0, 9, 9, 9, 9, 0, 9, 9, 9, 0, 9, 9, 9, 9, 0, 9, 0, 9, 0, 9, 9, 9, 9, 9, 0, 9, 0, 9, 9, 0, 9, },18 new int[] { 9, 0, 9, 0, 9, 9, 9, 0, 9, 0, 9, 9, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 9, 0, 0, 0, 9, 0, 9, 0, 0, 0, 0, 0, 9, 0, 9, 9, 0, 9, },19 new int[] { 9, 0, 9, 0, 9, 9, 9, 9, 9, 0, 9, 9, 0, 9, 9, 9, 0, 9, 9, 9, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 9, 9, 9, 9, 0, 9, 9, 0, 9, },20 new int[] { 9, 0, 9, 0, 0, 0, 0, 0, 9, 0, 9, 9, 0, 9, 9, 9, 0, 0, 9, 9, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 0, 0, 0, 0, 9, 0, 0, 9, },21 new int[] { 9, 0, 9, 9, 9, 0, 9, 9, 9, 0, 9, 9, 0, 0, 0, 9, 9, 0, 9, 0, 0, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 9, 9, 9, 9, 0, 9, 9, },22 new int[] { 9, 0, 9, 9, 9, 0, 9, 9, 9, 0, 0, 0, 0, 9, 0, 9, 9, 0, 9, 0, 9, 9, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 9, 9, 9, 9, 0, 9, 9, },23 new int[] { 9, 0, 0, 9, 9, 0, 0, 0, 9, 0, 9, 9, 0, 9, 0, 9, 9, 0, 9, 0, 9, 9, 9, 0, 9, 0, 9, 0, 9, 0, 9, 0, 9, 9, 9, 9, 9, 0, 9, 9, },24 new int[] { 9, 9, 0, 0, 9, 0, 9, 0, 9, 0, 9, 9, 9, 9, 0, 9, 9, 0, 9, 0, 0, 0, 0, 0, 9, 0, 0, 0, 9, 0, 9, 0, 0, 0, 0, 0, 0, 0, 9, 9, },25 new int[] { 9, 9, 9, 0, 9, 9, 9, 0, 9, 0, 9, 9, 9, 9, 0, 9, 9, 0, 9, 9, 0, 9, 9, 9, 9, 9, 9, 0, 9, 0, 9, 0, 9, 0, 9, 9, 9, 9, 9, 9, },26 new int[] { 9, 9, 9, 0, 9, 9, 9, 0, 9, 0, 9, 9, 9, 9, 0, 9, 9, 0, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0, 0, 0, 9, 0, 9, 0, 9, 9, 9, 9, 9, 9, },27 new int[] { 9, 0, 0, 0, 9, 9, 9, 0, 9, 0, 9, 0, 0, 0, 0, 9, 9, 0, 9, 9, 9, 9, 9, 0, 9, 9, 9, 9, 9, 9, 9, 0, 9, 0, 9, 0, 0, 0, 0, 9, },28 new int[] { 9, 0, 9, 9, 9, 9, 9, 0, 9, 0, 9, 9, 0, 9, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 9, 9, 9, 9, 9, 9, 9, 0, 9, 0, 9, 0, 9, 9, 9, 9, },29 new int[] { 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 9, 0, 9, 0, 9, 9, 0, 9, 9, 9, 9, 9, 0, 9, 0, 0, 0, 0, 0, 0, 0, 9, 0, 9, 0, 9, 9, 9, 9, },30 new int[] { 9, 0, 9, 9, 9, 9, 9, 9, 9, 0, 9, 9, 0, 9, 0, 9, 9, 0, 0, 9, 9, 9, 9, 0, 9, 0, 9, 9, 9, 9, 9, 9, 9, 0, 9, 0, 9, 0, 9, 9, },31 new int[] { 9, 0, 9, 9, 9, 9, 9, 9, 9, 0, 9, 0, 0, 9, 9, 9, 9, 9, 0, 9, 0, 0, 0, 0, 0, 0, 9, 9, 9, 9, 9, 9, 9, 0, 9, 0, 9, 0, 9, 9, },32 new int[] { 9, 0, 9, 9, 9, 9, 9, 9, 9, 0, 9, 9, 0, 0, 9, 9, 9, 9, 0, 9, 0, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 0, 9, 0, 9, 0, 9, 9, },33 new int[] { 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 9, 0, 9, 9, 9, 9, 9, 0, 9, 0, 9, 9, 9, 9, 9, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 9, 0, 9, 9, },34 new int[] { 9, 0, 9, 9, 9, 0, 9, 9, 9, 0, 9, 9, 0, 0, 0, 0, 0, 0, 0, 9, 0, 9, 9, 0, 9, 9, 0, 9, 9, 9, 9, 9, 0, 9, 9, 0, 0, 0, 9, 9, },35 new int[] { 9, 0, 9, 9, 9, 0, 9, 9, 9, 0, 9, 9, 9, 9, 0, 9, 0, 9, 0, 9, 0, 9, 9, 0, 9, 9, 0, 9, 9, 0, 0, 0, 0, 9, 9, 0, 9, 0, 9, 9, },36 new int[] { 9, 0, 9, 9, 9, 0, 9, 9, 9, 0, 0, 0, 9, 9, 0, 9, 0, 9, 9, 9, 0, 0, 9, 0, 0, 0, 0, 9, 9, 9, 0, 9, 9, 9, 9, 0, 9, 0, 9, 9, },37 new int[] { 9, 0, 9, 9, 9, 0, 9, 9, 9, 0, 9, 0, 9, 9, 0, 9, 0, 9, 9, 9, 0, 0, 9, 9, 0, 0, 9, 9, 0, 9, 0, 9, 9, 9, 9, 0, 9, 0, 9, 9, },38 new int[] { 9, 0, 0, 0, 9, 0, 0, 0, 9, 0, 9, 0, 9, 0, 0, 9, 0, 9, 9, 9, 9, 0, 9, 9, 9, 0, 9, 9, 0, 9, 9, 9, 0, 9, 9, 0, 9, 9, 9, 9, },39 new int[] { 9, 9, 9, 0, 9, 0, 9, 9, 9, 0, 9, 0, 9, 0, 9, 9, 0, 0, 0, 0, 9, 0, 9, 9, 9, 0, 9, 9, 0, 9, 9, 9, 0, 9, 9, 0, 9, 9, 9, 9, },40 new int[] { 9, 9, 9, 0, 9, 0, 9, 9, 9, 0, 9, 0, 9, 0, 9, 9, 9, 9, 9, 0, 9, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 9, 9, 9, },41 new int[] { 9, 0, 0, 0, 9, 0, 9, 0, 9, 0, 9, 9, 9, 0, 0, 9, 0, 0, 0, 0, 9, 0, 9, 9, 9, 0, 9, 9, 9, 9, 0, 9, 9, 9, 9, 0, 9, 9, 9, 9, },42 new int[] { 9, 0, 9, 9, 9, 0, 9, 0, 0, 0, 9, 9, 9, 9, 0, 9, 0, 9, 9, 9, 9, 0, 9, 9, 9, 0, 9, 9, 9, 9, 0, 9, 9, 9, 9, 0, 9, 9, 9, 9, },43 new int[] { 9, 0, 0, 0, 0, 0, 9, 9, 9, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 9, 9, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, },44 new int[] { 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, }45 };46 Console.WriteLine("迷宫地图：");47 PrintMap();48 System.Console.ReadKey();49 }50 private static void PrintMap() {51 Console.ForegroundColor = ConsoleColor.Green;52 for (int i = 0; i < map.Length; i++) {53 for (int j = 0; j < map.Length; j++)54 if (map[i][j] == 9)55 Console.Write("■");56 else57 Console.Write(" ");//Console.Write("※");58 Console.WriteLine();59 }60 }61 }
先看看运行结果：
递归的方法跟之前的差不多，不过这次并不直接打印出来而只是做保存，把每一步的坐标点都记录下来
static List<List<string>> results = new List<List<string>>(); static List<string> way = new List<string>(); static void Go(int i, int j) { int m, n; map[i][j] = 1; if (i == endY && j == endX) { way.Clear(); for (m = 0; m < map.Length; m++) { for (n = 0; n < map.Length; n++) if (map[m][n] == 1) { way.Add("" + m + "," + n); } } results.Add((way.ToArray().Clone() as string[]).ToList<string>()); } if (map[i][j + 1] == 0) Go(i, j + 1); if (map[i + 1][j] == 0) Go(i + 1, j); if (map[i][j - 1] == 0) Go(i, j - 1); if (map[i - 1][j] == 0) Go(i - 1, j); map[i][j] = 0; }
然后在所有线路集合中找出最优线路也就是最短线路
List<string> bestWay = BestWayOut(); //找到最优解 MarkWayInMap(bestWay); //用最优解标记地图 Console.ReadKey(); StepByStep(startX, startY); //用字典记录坐标的步数[递归] WatchBestStep(); //输出最优步伐
static public List<string> BestWayOut() { Console.WriteLine(); Console.WriteLine(); Console.WriteLine(); Console.WriteLine("==================最优路线是=================="); var r = results.OrderBy(result => result.Count).First(); for (int i = 0; i < map.Length; i++) { for (int j = 0; j < map[i].Length; j++) { string str = i + "," + j; if (r.Contains(str)) { Console.ForegroundColor = ConsoleColor.Red; Console.Write("◆"); Console.ResetColor(); } else { switch (map[i][j]) { case 9: Console.ForegroundColor = ConsoleColor.Green; Console.Write("■"); Console.ResetColor(); break; default: Console.Write(" "); break; } } } Console.WriteLine(); } return r; } static public void MarkWayInMap(List<string> r) { for (int i = 0; i < map.Length; i++) { for (int j = 0; j < map[i].Length; j++) { string str = i + "," + j; if (r.Contains(str)) { map[i][j] = 1; } } } } static int count = 1;//用于记录坐标点的步数 static public void StepByStep(int x, int y) { map[x][y] = 2; dicStep[string.Format("{0},{1}", x, y)] = count++; if (x == endX && y == endY) { } else if (map[x][y + 1] == 1) { StepByStep(x, y + 1); } else if (map[x + 1][y] == 1) { StepByStep(x + 1, y); } else if (map[x][y - 1] == 1) { StepByStep(x, y - 1); } else if (map[x - 1][y] == 1) { StepByStep(x - 1, y); } } static public void WatchBestStep() { Console.WriteLine(); Console.WriteLine(); Console.WriteLine(); Console.WriteLine("==================最优路线走法=================="); for (int i = 0; i < map.Length; i++) { for (int j = 0; j < map[i].Length; j++) { string str = i + "," + j; if (dicStep.ContainsKey(str)) { Console.BackgroundColor = ConsoleColor.Red; Console.Write(string.Format("{0,2}", dicStep[str] % 10)); Console.ResetColor(); } else { switch (map[i][j]) { case 9: Console.ForegroundColor = ConsoleColor.Green; Console.Write("■"); Console.ResetColor(); break; default: Console.Write(" "); break; } } } Console.WriteLine(); } }
这个简单的40*40迷宫就有23280条线路，使用递归的速度还是比较慢的总共用时 接近7s，所以这个并不是最好的不过用来研究经典迷宫还是足够了，咱们只为了玩嘛是吧！
迷宫问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。