迷宫求解明

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         /// <summary>
 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         /// </summary>
 40         /// <param name="start"></param>
 41         /// <param name="end"></param>
 42         /// <param name="maze"></param>
 43         /// <param name="diradd"></param>
 44         static void MazePath(Point start, Point end, int[,] maze, int[,] diradd)
 45         {
 46             Point p;
 47             Element elem;
 48             Stack<Element> S1 = new Stack<Element>();
 49             Stack<Element> S2 = new Stack<Element>();
 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 }
迷宫求解 明

迷宫求解明
