C#以不同算法写的迷宫算法

首页 > CShap > C#以不同算法写的迷宫算法

C#以不同算法写的迷宫算法

2009年12月30日 a18ccms 发表评论阅读评论

简单文字描述如下：

设定当前位置的初值为入口位置；

do｛

若当前位置可通，

则｛将当前位置插入栈顶； // 纳入路径

若该位置是出口位置，则结束；

// 求得路径存放在栈中

否则切换当前位置的东邻方块为新的当前位置；

｝

否则
{

若栈不空且栈顶位置尚有其他方向未被探索，

则设定新的当前位置为: 沿顺时针方向旋转

找到的栈顶位置的下一相邻块；

若栈不空但栈顶位置的四周均不可通，

则｛删去栈顶位置； // 从路径中删去该通道块

若栈不空，则重新测试新的栈顶位置，

直至找到一个可通的相邻块或出栈至栈空；

｝

｝while (栈不空）

思路尝试(失败了，看下面的三种算法)

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace MazeSecond
{

    public struct StateItem
    {
        public int dir;
        public Point point;
        public int sex;
    }
    public struct Point
    {
        public int x;
        public int y;
    }
    class Program
    {
        static  Stack UptoDownStack = new Stack();
        static Stack DownToUpStack = new Stack();
        static void Main(string[] args)
        {
            //初始化迷宫
            int[,] MazeItem = new int[10, 10]
            {
                {1,1,1,1,1,1,1,1,1,1},
                {1,0,1,1,1,0,0,0,1,1},
                {1,0,0,1,1,0,1,0,1,1},
                {1,0,0,0,0,0,1,0,1,1},
                {1,1,0,1,0,1,1,0,1,1},
                {1,1,0,1,0,1,1,0,1,1},
                {1,0,0,0,1,1,1,0,1,1},
                {1,1,0,0,0,0,0,0,1,1},
                {1,1,1,1,1,1,0,0,0,1},
                {1,1,1,1,1,1,1,1,1,1}
            };
            //输出迷宫
            for (int i = 0; i <= MazeItem.GetUpperBound(0); i++)
            {
                for (int j = 0; j <= MazeItem.GetUpperBound(1); j++)
                {
                    Console.Write(MazeItem[i, j]);
                }
                Console.WriteLine();
            }
            //起点初始化
            StateItem UptoDownItem = new StateItem();
            UptoDownItem.dir = 1;
            UptoDownItem.point = new Point();
            UptoDownItem.point.x = 1;
            UptoDownItem.point.y = 1;
            UptoDownItem.sex = 0;
            //终点初始化
            StateItem DowntoUPItem = new StateItem();
            DowntoUPItem.dir = 1;
            DowntoUPItem.point = new Point();
            DowntoUPItem.point.x = 8;
            DowntoUPItem.point.y = 8;
            DowntoUPItem.sex = 1;

            UptoDownStack.Push(UptoDownItem);
            DownToUpStack.Push(DowntoUPItem);
            do
            {
               StateItem UptoDown=ReturnStatItem(UptoDownItem);
               StateItem DowntoUP = ReturnStatItem(DowntoUPItem);
                UptoDownStack.Push(UptoDown);
                DownToUpStack.Push(DowntoUP);
                if (UptoDown.point.x == DowntoUP.point.x && UptoDown.point.y == DowntoUP.point.y)
                {
                    break;
                }

            } while (UptoDownStack.Count > 0);

            while(DownToUpStack.Count > 0)
            {
                UptoDownStack.Push(DownToUpStack.Pop());
            }

            if (UptoDownStack.Count > 0)
            {
                while (UptoDownStack.Count > 0)
                {
                    StateItem st = (StateItem)UptoDownStack.Pop();
                    Console.WriteLine(st.point.x + "," + st.point.y);
                }
            }
            else
            {
                Console.WriteLine("无");
            }
        }
        public static StateItem ReturnStatItem(StateItem stateItem)
        {
            //初始化迷宫
              int[,] MazeItem = new int[10, 10]
            {
                {1,1,1,1,1,1,1,1,1,1},
                {1,0,1,1,1,0,0,0,1,1},
                {1,0,0,1,1,0,1,0,1,1},
                {1,0,0,0,0,0,1,0,1,1},
                {1,1,0,1,0,1,1,0,1,1},
                {1,1,0,1,0,1,1,0,1,1},
                {1,0,0,0,1,1,1,0,1,1},
                {1,1,0,0,0,0,0,0,1,1},
                {1,1,1,1,1,1,0,0,0,1},
                {1,1,1,1,1,1,1,1,1,1}
            };

            switch (stateItem.dir)
            {
                case 1:
                    stateItem.point.y = stateItem.point.y - 1;
                    break;
                case 2:
                    stateItem.point.x = stateItem.point.x + 1;
                    break;
                case 3:
                    stateItem.point.y = stateItem.point.y + 1;
                    break;
                case 4:
                    stateItem.point.x = stateItem.point.x - 1;
                    break;
                default :
                    break;
            }
            if (MazeItem[stateItem.point.x, stateItem.point.y] == 0)
            {
                return stateItem;
                MazeItem[stateItem.point.x, stateItem.point.y] = 2;
                stateItem.dir = 1;
            }
            else
            {
                if (stateItem.dir != 4)
                {
                    stateItem.dir++;
                    switch (stateItem.dir)
                    {
                        case 1:
                            stateItem.point.y = stateItem.point.y + 1;
                            break;
                        case 2:
                            stateItem.point.x = stateItem.point.x - 1;
                            break;
                        case 3:
                            stateItem.point.y = stateItem.point.y - 1;
                            break;
                        default:
                            break;
                    }
                    return stateItem;
                }
                else
                {
                    if (stateItem.sex == 0)
                    {
                        UptoDownStack.Pop();//第一次抛栈
                        stateItem = (StateItem)UptoDownStack.Pop();//第二次抛栈
                        if (stateItem.dir != 4)
                        {
                            stateItem.dir++;
                        }
                        return stateItem;
                    }
                    else
                    {
                        DownToUpStack.Pop();
                        stateItem = (StateItem)DownToUpStack.Pop();
                        if (stateItem.dir != 4)
                        {
                            stateItem.dir++;
                        }
                        return stateItem;
                    }
                }
            }
        }
    }
}

第一个算法：

/// <summary>
/// 走迷宫
/// </summary>
/// <param name="maze">迷宫矩阵</param>
/// <param name="curr">当前位置</param>
/// <param name="dest">目标位置</param>
/// <returns>返回是否走到终点</returns>
private bool SpyMaze(ref int[,] maze, Point curr, Point dest)
{
    if (!Rectangle.FromLTRB(0, 0, maze.GetLength(0),
        maze.GetLength(1)).Contains(curr)) return false; // 走到边界
    if (maze[curr.X, curr.Y] != 0) return false; // 墙或者是已经走过
    maze[curr.X, curr.Y] = 2; // 标记已经走过
    if (curr == dest) return true; // 走到目的地
    Point[] offset = {
        new Point(00, -1), new Point(+1, 00),
        new Point(00, +1), new Point(-1, 00)
    };
    bool result = false;
    for (int i = 0; !result && i < offset.Length; i++)
    {
        Point move = curr;
        move.Offset(offset[i]);
        result = SpyMaze(ref maze, move, dest);
    }
    if (!result) maze[curr.X, curr.Y] = 0; // 还原
    return result;
}

private void button1_Click(object sender,EventArgs e)
{
    int[,] maze = {
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0},
        {1,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0},
        {1,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0},
        {1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0},
        {1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0},
        {1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0},
        {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0},
    };
    SpyMaze(ref maze, new Point(0, 0),
        new Point(maze.GetLength(0) - 1, maze.GetLength(1) - 1));
    for (int i = 0; i < maze.GetLength(0); i++)
    {
        for (int j = 0; j < maze.GetLength(1); j++)
        {
            if (maze[i, j] == 2)
                Console.Write("[color=#FF0000]{0}[/color]", maze[i, j]);
            else Console.Write(maze[i, j]);
        }
        Console.WriteLine();
    }
}

结果：
2222222222222000000000000000000000000000
1111111111112111111111111111111110111111
1222222222222100000000000000000010122222
1211111111110101111111111111111010121112
1210000000000101000000000000001010121012
1211111111111101111111111111101010121012
1222222222222222222200000000101010121012
1011111111111111111211111111101010121012
1010000000000000001210000000001010121012
1010111111111111111211111011101010121012
1010100000000000000222221010101010121012
1010101111111111111111121010101010121012
1010101000000000000000121010101010121012
1010101011111111111110121010101010121012
1010101012222222222210121010101010121012
1010101012111111111210121010101010121012
1010101012100000001210121010101010121012
1010101012101111111210121010101010121012
1010101012101222222210121010101010121012
1010111012101211111110121010101010121012
1010000012101210000000121010101010121012
1010111012101211111111121010101010121012
1010101012101222222222221010101010121012
1010101012101111111111111010101010121012
1010101012100000000000000010101010121012
1010101012111111111111111110101010121012
1010101012222222222222222200101010121012
1010101011111111111111111211101010121012
1010101000000000000000001210001010121012
1010101111111111111111111211101010121012
1010100000000000000000000222101010121012
1010111111111111111111111112101010121012
1010000000000000000000000012101010121012
1011111111111110111111111012101010121012
1000000000000010100000000012101010121012
1011111111111110101111111012101110121012
1010000000000000101000000012100000121012
1011111111111111101011111112111111121012
1000000000000000001010000002222222221012
1111111111111111111011111111111111111012
0000000000000000000000000000000000000012

再来一种算法：

using System;
using System.Collections.Generic;
using System.Text;
namespace 迷宫问题_BFS
{
    class Program
    {
        struct Point
        {
            public int X;
            public int Y;
        }
        struct MapState
        {
            public int[,] Map;
            public Point Current;
            public bool Flag;
        }
        const int WIDTH=10;
        const int HEIGHT=10;
        static MapState[] list = new MapState[100000];
        static int[,] box = new int[WIDTH, HEIGHT]
            {
                {1,1,1,1,1,1,1,1,1,1},
                {1,0,1,1,1,0,0,0,1,1},
                {1,0,0,1,1,0,1,0,1,1},
                {1,0,0,0,0,0,1,0,1,1},
                {1,1,0,1,0,1,1,0,1,1},
                {1,1,0,1,0,1,1,0,1,1},
                {1,0,0,0,1,1,1,0,1,1},
                {1,1,0,0,0,0,0,0,1,1},
                {1,1,1,1,1,1,0,0,0,1},
                {1,1,1,1,1,1,1,1,1,1}
            };
        static void Main(string[] args)
        {
            Console.WriteLine("原来的样子：");
            for(int i=0;i<WIDTH;i++)
            {

                for (int y = 0; y < HEIGHT; y++)
                {
                    if (box[i, y] == 1)
                    {
                        Console.ForegroundColor = ConsoleColor.Green  ;
                        Console.Write(" "+ box[i, y].ToString ());

                    }
                    else if (box[i, y] == 0)
                    {
                        Console.ForegroundColor = ConsoleColor.White ;
                        Console.Write(" "+ box[i, y].ToString ());

                    }
                    else if (box[i, y] ==2)
                    {
                        Console.ForegroundColor = ConsoleColor.Red ;
                        Console.Write(" "+box[i, y].ToString());
                    }
                }
                Console.WriteLine();
            }
            Walk();
            Console.WriteLine("走出的样子：");
            for (int i = 0; i < WIDTH; i++)
            {
                for (int y = 0; y < HEIGHT; y++)
                {
                    if (list[Resualt1].Map[i, y] == 1 && list[Resualt2].Map[i, y] == 1)
                    {
                        Console.ForegroundColor = ConsoleColor.Green;
                        Console.Write(" 1");

                    }
                    else if (list[Resualt1].Map[i, y] == 0 && list[Resualt2].Map[i, y] ==0)
                    {
                        Console.ForegroundColor = ConsoleColor.White;
                        Console.Write(" 0");

                    }
                    else if (list[Resualt1].Map[i, y] == 2 || list[Resualt2].Map[i, y] == 2)
                    {
                        Console.ForegroundColor = ConsoleColor.Red;
                        if (list[Resualt1].Map[i, y] == 2)
                        {
                            Console.Write(" " + list[Resualt1].Map[i, y].ToString());
                            continue;
                        }
                        if (list[Resualt2].Map[i, y] == 2)
                        {
                            Console.Write(" " + list[Resualt2].Map[i, y].ToString());
                            continue;
                        }
                    }
                }
                Console.WriteLine();
            }
            Console.Read();
        }
        static void Print(int[,] box)
        {
            for (int i = 0; i < WIDTH; i++)
            {
                Console.WriteLine();
                for (int y = 0; y < HEIGHT; y++)
                {
                    if (box[i, y] == 1)
                    {
                        Console.ForegroundColor = ConsoleColor.Green;
                        Console.Write(" " + box[i, y].ToString());

                    }
                    else if (box[i, y] == 0)
                    {
                        Console.ForegroundColor = ConsoleColor.White;
                        Console.Write(" " + box[i, y].ToString());

                    }
                    else if (box[i, y] == 2)
                    {
                        Console.ForegroundColor = ConsoleColor.Red;
                        Console.Write(" "+box[i, y].ToString());
                    }
                }
            }
        }
        static int Resualt1 = 0;
        static int Resualt2 = 0;
        static int f = 0; static int l = 1;
        static void Walk()
        {
            list[f] = CreateMapState(1,1,box,true);
            list[f + 1] = CreateMapState(8, 8, box,false);
            do
            {
                Move(list[f], 0, 1,list[f].Flag );
                Move(list[f], 1, 0, list[f].Flag);
                Move(list[f], 0, -1, list[f].Flag);
                Move(list[f], -1, 0, list[f].Flag);
                f++;
            }
            while (CheckOut());
        }
        static bool CheckOut()
        {
            for (int i =0  ; i < l; i++)
            {
                for (int k = i+1; k < l-1; k++)
                {
                    if (list[i].Current.X == list[k].Current.X && list[i].Current.Y == list[k].Current.Y && list[i].Flag!=list[k].Flag )
                    {
                        Resualt1 = i;
                        Resualt2 = k;
                        return false;
                    }
                }
            }
            return true;
        }
        static void Move(MapState map,int x,int y,bool flag)
        {
            if (map.Map[map.Current.X + x, map.Current.Y + y] != 1 && map.Map[map.Current.X + x, map.Current.Y + y] != 2)
            {
                if (map.Current.X + x > 0 && map.Current.Y + y > 0)
                {
                    l++;
                    list[l] = CreateMapState(map.Current.X + x, map.Current.Y + y, map.Map, flag);
                }
            }

        }
        static MapState CreateMapState(int x,int y,int[,] tmp,bool flag)
        {
            MapState box;
            box.Flag = flag;
            box.Map = (int[,])tmp.Clone ();
            box.Map [x, y] = 2;
            box.Current.X = x;
            box.Current.Y = y;
            return box;
        }
    }
}

其实2头和1头开始都是一回事
你一开始就压个坐标进队列
一个是入口，一个是出口
然后宽度优先搜索·····
最后如果出口和入口的坐标推出的路线有点重叠就找到出路了···
但是每走都要记下当前地图的状态
CreateMapState干的就是这个
Walk是开始走迷宫
CheckOut是检查出口和入口推出的路线有无重叠点
如果没有就继续推如果有就EXIT···打出路线
Print是我调试用的。。没用……

struct MapState
        {
            public int[,] Map;地图的位置状态
            public Point Current;但前走到哪个点
            public bool Flag;是入口推出点还是出口推出的点
        }

在WinForm下
System.Console.WriteLine("Debug日志");
和
System.Diagnostics.Debug.WriteLine("Debug日志");
相当

Console.Write("[color=#FF0000]{0}[/color]", maze[i, j]);
这类是细节输出的问题，自己动手改改就可以了。

再写个算法：

using System;

namespace ConsoleApplication1
{
    class Program
    {
        static int[,] MazeItem = new int[10, 10]   //初始化迷宫
            {
                {1,1,1,1,1,1,1,1,1,1},
                {1,0,1,1,1,0,0,0,1,1},
                {1,0,0,1,1,0,1,0,1,1},
                {1,0,0,0,0,0,1,0,1,1},
                {1,1,0,1,0,1,1,0,1,1},
                {1,1,0,1,0,1,1,0,1,1},
                {1,0,0,0,1,1,1,0,1,1},
                {1,1,0,0,0,0,0,0,1,1},
                {1,1,1,1,1,1,0,0,0,1},
                {1,1,1,1,1,1,1,1,1,1}
            };

        static void Main(string[] args)
        {
            if (!LetsGo(1, 1, 1, 5))
                Console.WriteLine("走不通。");
            else
                Console.WriteLine("    打印的是从出口到入口的路径。");
        }

        static bool LetsGo(int startX, int starY, int endX, int endY)
        {
            if (startX < 0 || startX >= 10 || endX < 0 || endX >= 10 || MazeItem[startX, starY] == 1)
                return false;

            MazeItem[startX, starY] = 1;    //避免重复
            if ((startX == endX && starY == endY) ||
                LetsGo(startX - 1, starY, endX, endY) || LetsGo(startX + 1, starY, endX, endY) ||
                LetsGo(startX, starY + 1, endX, endY) || LetsGo(startX, starY - 1, endX, endY))
            {
                print(startX, starY);
                return true;
            }
            else
                return false;
        }

        static void print(int x, int y)
        {
            Console.Write(string.Format("[{0},{1}]", x, y));
        }
    }
}

除非你多线程使用到多核，并且你合理地解决了数据重复问题，有可能快一点 --> 除非你多线程使用到多核，并且你合理地解决了数据并发冲突问题，有可能快一点
但这种快跟算法无关。
呵，我的程序跟上面的程序的逻辑是一样重复的。
其实，对于这类最简单的遍历，你知道“避免重复”就一切通吃了。至于搞什么树、栈结构，都是非常次要的。你的算法一样，只不过是经过每一个路径时“顺便留下的脚印”放在不同的结构中罢了。

树是最浪费资源的，而栈（不论函数栈还是显示自定义栈）对资源的使用主要跟深度有关。要想让“深度”最低，在每一次决定“向左、向右、向上、向下”这个次序的时候就不能无头苍蝇地机械决定，到达目的地距离最短的方向优先被选择则占用的栈最浅。但是，如果搜索过程中就知道哪条分支到达目的地最近，这就成了神仙了。所以一般的搜索策略都会开发不同的“启发函数”来决定搜索方向的排序，但是这个启发函数的好坏其实也往往是撞大运。

因此，不论你怎么搜，问题本身就是如此简单，没有什么真正管用的启发函数，那么就没有什么高明的策略。

这不像下棋。两个棋手的脑筋同样的“容量”，都是能够看到三步以外，但是一个棋手对形势判断的启发函数优于另一个，那么同样的算法下第一个人可以获胜。

分类: CShap 标签: 算法, 迷宫

天草迷宫独特算法 (0)
代码下载原文地址因为实验要求写迷宫算法的缘故，不得不研究一下这个看似没用的东西。实验要...
一个C#的迷宫生成算法，采用深度优先遍历拆墙 (0)
因为最近要用C#开发一个走迷宫的小游戏，所以需要编写一个随机生成迷宫的组件，但是查阅了网上的...

评论 (0) Trackbacks (0) 发表评论 Trackback

本文目前尚无任何评论.

本文目前尚无任何 trackbacks 和 pingbacks.

C#里也可以用上Eval函数[即时运算] “空手道”玩转54套上海豪宅？

A18制造

C#以不同算法写的迷宫算法

相关文章

博客动态

近期文章

分类目录

友情链接表

最新评论

功能