2013-01-22
摘要：用“穷举”的方法，从入口出发，顺某一方向向前探索。若能走通，继续；不能，原路返回，换方向继续。这样；遍历所有的道路，直到发现出口。因为要原路返回，也需要栈。
View Code 1 using System; 2 using System.Collections.Generic; 3 4 namespace MazePath 5 { 6 //方向 7 public enum Direct{NA=-1,East=0,South=1,West=2,North=3,Out=886}; 8 9 struct Point 10 { 11 public int x; 12 public int y; 13 } 14 struct Element 15 { 16 public Point p; 17 public Direct d; 18 } 19 20 class Program 21 { 22 static void Main(string[] args) 23 { 24 Point start = GetStartMark(); 25 Point end = GetEndMark(); 26 int[,] maze = InitMaze(); 27 int[,] diradd = InitDirAdd(); 28 MazePath(start, end, maze, diradd); 29 Console.Read(); 30 } 31 32 /// 33 /// step 1 依次尝试东南西北四个方向， 34 /// step 1.1 如果下一步可通，标记下一位置已访问，把当前位置和方向入栈 35 /// step 1.1.1 若下一位置为出口，显示所有路径，返回 36 /// step 1.1.2 若不是，则可通往的位置为当前位置 37 /// step 1.2 如果不通，换个方向 38 /// step 2 如果不通或已走过，退栈取得上一次位置和方向，换其他方向 39 /// 40 /// 41 /// 42 /// 43 /// 44 static void MazePath(Point start, Point end, int[,] maze, int[,] diradd) 45 { 46 Point p; 47 Element elem; 48 Stack S1 = new Stack (); 49 Stack S2 = new Stack (); 50 maze[start.x, start.y] = 2; //入口点作上标记 51 p = start; 52 elem.p = p; 53 elem.d = Direct.East; 54 do 55 { 56 //step 1. 依次尝试东南西北四个方向 57 while (elem.d < Direct.North) 58 { 59 p = GetNextPoint(elem.p, elem.d, diradd); 60 //step 1.1 若当前位置可通，标记可通往的位置，并入栈当前位置、方向 61 if (maze[p.x, p.y] == 0) 62 { 63 maze[p.x, p.y] = 2; 64 S1.Push(elem); 65 //step 1.1.1 若下一位置为出口，显示所有路径，返回。 66 if (p.x == end.x && p.y == end.y) 67 { 68 elem.p = p; 69 elem.d = Direct.Out; //方向输出为-1 判断是否到了出口 70 S1.Push(elem); 71 Console.WriteLine("\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n"); 72 while (S1.Count != 0) //逆置序列 并输出迷宫路径序列 73 { 74 S2.Push(S1.Pop()); 75 } 76 while (S2.Count != 0) 77 { 78 elem = S2.Pop(); 79 Console.WriteLine("坐标'{0},{1}',方向{2}->", elem.p.x, elem.p.y, elem.d); 80 } 81 return; 82 } 83 //step 1.1.2 若不是，则可通往的位置为当前位置 84 else 85 { 86 elem.p = p; 87 elem.d = Direct.East; 88 } 89 } 90 // step 1.2 如果不通，换个方向 91 else 92 { 93 elem.d = TurnClockwise(elem.d); 94 } 95 } 96 //step 2 如果不通或已走过，退栈取得上一次位置和方向，换其他方向 97 if (S1.Count != 0) 98 { 99 elem = S1.Pop();100 elem.d = TurnClockwise(elem.d);101 }102 }103 while (S1.Count != 0);104 105 Console.WriteLine("没有找到可以走出此迷宫的路径\n");106 }107 108 static int[,] InitMaze()109 {110 //横坐标向右为正，纵坐标向下为正111 /// + ----+112 /// | |113 /// | | | |114 /// | | |115 /// | +---+116 /// | 117 /// +------118 119 //0为可通，1为不可通120 int[,] maze = new int[,] { { 1, 1, 1, 1, 1, 1, 1 }, { 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 1, 1, 1, 0, 1 }, { 1, 0, 0, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1, 0, 1 }, { 1, 0, 0, 0, 1, 0, 0 }, { 1, 1, 1, 1, 1, 0, 1 } };121 return maze;122 }123 124 //得到迷宫的入口点125 static Point GetStartMark()126 {127 Point mark;128 mark.x = 1;129 mark.y = 0;130 return mark;131 }132 //得到迷宫的出口点133 static Point GetEndMark()134 {135 Point mark;136 mark.x = 6;137 mark.y = 5;138 return mark;139 }140 //按东西南北走，相对应x，y坐标的增减141 static int[,] InitDirAdd()142 {143 int[,] dirAdd = new[,] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };144 return dirAdd;145 }146 //顺时针旋转147 static Direct TurnClockwise(Direct d)148 {149 return d + 1;150 }151 152 //下一步153 static Point GetNextPoint(Point p, Direct d, int[,] diradd)154 {155 Point q;156 q.x = p.x + diradd[(int)d, 0];157 q.y = p.y + diradd[(int)d, 1];158 return q;159 }160 }161 }