C# 数据结构与算法系列 (XIII)：递归 - 迷宫问题

public class Maze { public static void Test() { int[][] map = new int[8][]; for (int i = 0; i < map.Length; i++) { map[i] = new int[7]; } for (int i = 0; i < 7; i++) { map[0][i] = 1; map[7][i] = 1; } for (int i = 0; i < 8; i++) { map[i][0] = 1; map[i][6] = 1; } map[3][1] = 1; map[3][2] = 1; System.Console.WriteLine("初始化地图\n"); for (int i = 0; i < map.Length; i++) { for (int j = 0; j < map[i].Length; j++) { System.Console.Write(map[i][j] + "\t"); } System.Console.WriteLine(); } SetWay(map, 1, 1); System.Console.WriteLine("\n小球走过，并标识过的地图情况\n"); for (int i = 0; i < map.Length; i++) { for (int j = 0; j < map[i].Length; j++) { System.Console.Write(map[i][j]+"\t"); } System.Console.WriteLine(); } } /// <summary> /// 1.map表示地图 /// 2.i,j表示地图的那个位置开始出发（1,1） /// 3.如果小球能到map[6][5]位置，则说明通路找到 /// 4.约定：当map[i][j]为0表示该点没有走过，1表示为墙，2表示通路可以走，3表示该点已经走过，但是走不通 /// 5.在走迷宫时，需要确定一个策略（方法）下=》右=》上=》左，如果该点走不通，再回溯 /// </summary> /// <param name="map">地图</param> /// <param name="i">纵坐标</param> /// <param name="j">横坐标</param> protected static bool SetWay(int[][] map, int i, int j) { if (map[6][5] == 2) //表示通路 { return true; } else { if (map[i][j] == 0) { map[i][j] = 2; //假设该点可以走通 if (SetWay(map, i + 1, j)) //向下走 { return true; } else if (SetWay(map, i, j + 1)) //向右走 { return true; } else if (SetWay(map, i - 1, j)) //向上走 { return true; } else if (SetWay(map, i, j - 1)) //向左走 { return true; } else { //说明该点走不通，是死路 map[i][j] = 3; return false; } } else //如果map[i][j]!=0;那么就是1,2,3 { return false; } } } }