题目：给出下面迷宫，0表示通路，1表示障碍物，请找出入口（0，0）至出口（7，7）的路
思路：
1.设置三个指针，last ，now，next 起始位置都设置在入口。
2.实现一个寻找候选点的方法，候选点中不应该包含当前点的位置
3.判断是否有候选点，且是否为出口。
4.如果没有候选点，退回一步，判断是不是入口。
5.如果上一个点不是入口，删除上一个点的第一个候选点，然后试上一个点的第二个候选点
6.如果上一个点没有其他的候选点，再退回一步，从路径中删除这些错误的点
7.重复步骤，直达找到出口
Step 1 ：先实现一个Point类：
1 class Point 2 { 3 int x; 4 int y; 5 public int Position_X 6 { 7 get { return x; } 8 set { x = value; } 9 } 10 public int Position_Y 11 { 12 get { return y; } 13 set { y = value; } 14 } 15 public Point() { } 16 public Point(int x, int y) 17 { 18 Position_X = x; 19 Position_Y = y; 20 } 21 }
Step 2 ：定义全局变量，保存可以走的点的List和这些点的可以走的下一个点的List 以及三个指针和是否结束的flag
1 List<Point> way = new List<Point>(); 2 List<List<Point>> candicates = new List<List<Point>>(); 3 Point sureLast = null; 4 Point sureNow = null; 5 Point notSureNext = null; 6 bool finish = false;
Step 3 ：判断一个点是否是出口
1 public bool IsExit(Point p, int[][] maze) 2 { 3 if (p.Position_X == maze.Length - 1 && p.Position_Y == maze[maze.Length - 1].Length - 1) return true; 4 else return false; 5 }
Step 4：获取候选点，并且把上一步走的点排除在候选点之外
1 public bool GetNextCandicates(Point p, int[][] maze, ref List<Point> nextp) 2 { 3 //如果上下左右的点是边界上的点时，将其设为1，即为不可行 4 int up = p.Position_X - 1 > 0 ? maze[p.Position_X - 1][p.Position_Y] : 1; 5 int down = p.Position_X + 1 < maze[p.Position_X].Length ? maze[p.Position_X + 1][p.Position_Y] : 1; 6 int left = p.Position_Y - 1 > 0 ? maze[p.Position_X][p.Position_Y - 1] : 1; 7 int right = p.Position_Y + 1 < maze.Length ? maze[p.Position_X][p.Position_Y + 1] : 1; 8 if (up == 1 && down == 1 && left == 1 && right == 1) return false; //如果上下左右都不可行，返回false没有候选点 9 else 10 { 11 if (right != 1) 12 { 13 Point Right = new Point(p.Position_X, p.Position_Y + 1); 14 if ((sureNow == null)|| (Right.Position_X != sureNow.Position_X || Right.Position_Y != sureNow.Position_Y)) 15 { 16 nextp.Add(Right); 17 } 18 } 19 if (down != 1) 20 { 21 Point Down = new Point(p.Position_X + 1, p.Position_Y); 22 if ((sureNow == null) || (Down.Position_X != sureNow.Position_X || Down.Position_Y != sureNow.Position_Y)) 23 { 24 nextp.Add(Down); 25 } 26 } 27 if (left != 1) 28 { 29 Point Left = new Point(p.Position_X, p.Position_Y - 1); 30 if ((sureNow == null) || (Left.Position_X != sureNow.Position_X || Left.Position_Y != sureNow.Position_Y)) 31 { 32 nextp.Add(Left); 33 } 34 } 35 if (up != 1) 36 { 37 Point Up = new Point(p.Position_X - 1, p.Position_Y); 38 if ((sureNow == null) || (Up.Position_X != sureNow.Position_X || Up.Position_Y != sureNow.Position_Y)) 39 { 40 nextp.Add(Up); 41 } 42 } 43 if (nextp.Count > 0) { return true; } 44 else return false; 45 } 46 }
Step 5 ：处理一个错误的点
1 public bool DealWithWrongPoint (ref Point candicate) 2 { 3 bool isBreak = false; 4 way.Remove(sureNow); //删除保存的路里面的这个点 5 candicates.Remove(candicates[candicates.Count - 1]); //删除candates里面这个点的候选点 6 candicates[candicates.Count - 1].Remove(sureNow); //将这个点从上一个点的候选点里删掉 7 sureNow = sureLast; 8 if (way.Count > 2) 9 { 10 sureLast = way[way.Count - 2]; 11 if (candicates[candicates.Count - 1].Count > 0) 12 { 13 notSureNext = candicates[candicates.Count - 1][0]; 14 candicate = notSureNext; 15 return false; 16 } 17 else DealWithWrongPoint(ref candicate); 18 } 19 else 20 { 21 Console.WriteLine("There is no way to exit!"); 22 isBreak = true; 23 } 24 return isBreak; 25 }
Step 6 ：寻找通路
1 public void FindWay(Point candicate, int[][] maze) 2 { 3 while (!finish) 4 { 5 List<Point> nextp = new List<Point>(); 6 if (IsExit(candicate, maze)) 7 { 8 way.Add(candicate); 9 Console.WriteLine("Here you find the exit!"); 10 finish = true; 11 Print(maze); 12 break; 13 } 14 else 15 { 16 if (GetNextCandicates(candicate, maze, ref nextp))//如果有候选点 17 { 18 if (way.Count == 0) 19 { 20 //如果是起点，last和now不动 21 sureLast = new Point(0, 0); 22 sureNow = sureLast; 23 } 24 else if (way.Count == 1) 25 { 26 //如果是起点的下一个点，last不动 27 sureNow = candicate; 28 } 29 else 30 { 31 sureLast = sureNow; 32 sureNow = candicate; 33 } 34 way.Add(candicate); 35 notSureNext = nextp[0]; 36 candicates.Add(nextp); 37 //Console.WriteLine("last point is ({0},{1}) , now point is ({2},{3}) , next will try ({4},{5})", sureLast.Position_X, sureLast.Position_Y, sureNow.Position_X, sureNow.Position_Y, notSureNext.Position_X, notSureNext.Position_Y); 38 FindWay(notSureNext, maze); 39 } 40 else //没有候选点 41 { 42 43 if (candicate.Position_X == 0 && candicate.Position_Y == 0)//如果当前点为起点且找不到下一个可行点 44 { 45 Console.WriteLine("There is no way to exit!"); 46 break; 47 } 48 else 49 { 50 candicates[candicates.Count - 1].Remove(candicate); 51 if (candicates[candicates.Count - 1].Count > 0)//如果sureNow还有候选的下一个点 52 { 53 notSureNext = candicates[way.IndexOf(sureNow)][0]; 54 FindWay(notSureNext, maze); 55 } 56 else //SureNow 没有下一个候选点 57 { 58 if (DealWithWrongPoint(ref candicate)) 59 { 60 break; 61 } 62 else continue; 63 } 64 } 65 } 66 } 67 } 68 69 }
Step 7 ：打印迷宫
1 public void Print(int[][] maze) 2 { 3 for (int i = 0; i <maze.Length; i++) 4 { 5 for (int j = 0; j < maze[maze.Length - 1].Length; j++) 6 { 7 if (way.Where(a => a.Position_X == i && a.Position_Y == j).ToList().Count > 0) 8 { 9 Console.Write("■"); 10 } 11 else Console.Write("O"); 12 } 13 Console.Write(" "); 14 } 15 }
主函数，初始化迷宫获取出路
1 static void Main(string[] args) 2 { 3 int[][] maze = new int[8][]; 4 maze[0] = new int[] { 0, 1, 0, 0, 1, 1, 1, 1 }; 5 maze[1] = new int[] { 0, 1, 1, 0, 1, 0, 0, 1 }; 6 maze[2] = new int[] { 0, 0, 0, 0, 1, 0, 1, 1 }; 7 maze[3] = new int[] { 1, 1, 0, 0, 0, 0, 1, 1 }; 8 maze[4] = new int[] { 1, 1, 1, 1, 0, 1, 1, 1 }; 9 maze[5] = new int[] { 1, 0, 1, 0, 0, 0, 0, 1 }; 10 maze[6] = new int[] { 1, 0, 0, 0, 1, 1, 0, 1 }; 11 maze[7] = new int[] { 1, 1, 1, 0, 1, 1, 0, 0 }; 12 Program pg = new Program(); 13 pg.FindWay(new Point(0, 0), maze); 14 Console.ReadKey(); 15 }
运行结果：
初始迷宫：
程序找到的路
