用WPF做演示

1.用Stack记录和回溯

在现实生活中,在你迷路的时候,总是记录一些可记忆的建筑物作为返回的标志（比如你出去玩,总得回家的吧,那么就得记得回家的路）

(1)画迷宫

public class MazeElement : FrameworkElement{    public MazeElement(int[,] mg)    {        this.mg = mg;    }    int[,] mg=null;    protected override void OnRender(DrawingContext dc)    {        var width = 40;        dc.DrawRectangle(Brushes.Black, null, new Rect(0, 0, 10 * width, 10 * width));        for (int i = 0; i < 10; i++)        {            for (int j = 0; j < 10; j++)            {                if (mg[i, j] == 1)                {                    dc.DrawRectangle(Brushes.Gray, null, new Rect(j * (width), i * (width), width - 1, width - 1));                }                else                {                    dc.DrawRectangle(Brushes.White, null, new Rect(j * (width), i * (width), width - 1, width - 1));                }            }        }    }}

(2)白色表示可以通过的坐标,从坐标1,1寻找坐标(8,8)点

一个块的的数据结构如下,即坐标点加下个可寻找点的方向

public class Block{    public Point Point { get; set; }    public int Direction { get; set; }}

(3)若找到的下个是白点且没有重复的话,则继续寻找,否则就回溯,找另外的出口,其实就是穷举法了…

算法如下

public void MgPath(Point start, Point end){    Block temp = null;    bool find = false;    while (st.Count > 0)    {        temp = st.Peek();        _point = temp.Point;        Console.WriteLine(temp.Point.ToString());        var point = temp.Point;        var di = temp.Direction;        //UI Refresh don't care        System.Threading.Thread.Sleep(100);        Dispatcher.BeginInvoke(new Action(() =>        {            this.InvalidateVisual();        }), DispatcherPriority.Render);        if (point.Equals(end))        {            finished = true;            break;        }        //not find        find = false;        //find next block        while (di < 4 && !find)        {            di++;            switch (di)            {                case 0://top                    point.Y = temp.Point.Y - 1;                    point.X = temp.Point.X;                    break;                case 1://right                    point.X = temp.Point.X + 1;                    point.Y = temp.Point.Y;                    break;                case 2://bottom                    point.Y = temp.Point.Y + 1;                    point.X = temp.Point.X;                    break;                case 3://left                    point.X = temp.Point.X - 1;                    point.Y = temp.Point.Y;                    break;            }            if (mg[(int)point.X, (int)point.Y] == 0) find = true;        }        //if find        if (find)        {            temp.Direction = di;            st.Push(new Block() { Point = point, Direction = -1 });            //mark already visit            mg[(int)point.X, (int)point.Y] = -1;        }        else        {            //not find            mg[(int)temp.Point.X, (int)temp.Point.Y] = 0;            st.Pop();        }        break;    }}

这个例子还是发上源码吧，做演示用