前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >迷宫回溯

迷宫回溯

作者头像
JusterZhu
发布2022-12-07 20:29:44
5570
发布2022-12-07 20:29:44
举报
文章被收录于专栏:JusterZhuJusterZhu

概要

给定一个迷宫,指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(maze problem)。

  1. 小人的得到的路径和程序员设置的找路策略有关;即招录的上下左右的顺序相关。
  2. 再得到小球路径时,可以先使用(下右上左),再改成(上右下左),看看路径是不是有变化
  3. 测试回溯现象
  4. 如何求出最短路径?
代码语言:javascript
复制
   internal class Maze
    {
        public void Print(int[,] map) 
        {
            Console.WriteLine("迷宫地图:");
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 7; j++)
                {
                    Console.Write(map[i, j] + "   ");
                }
                Console.WriteLine();
            }
        }

        /// <summary>
        /// 使用递归回溯来给小球找路
        /// 1.map表示地图
        /// 2.i,j表示从地图的那个位置开始出发(1,1)
        /// 3.如果小球能到map[6,5]位置(迷宫出口),则说明通路找到
        /// 4.约定:当map[i,j]为0表示该点没有走过当为1表示墙;2表示通路可以走;3表示该点以及走过,但是走不通
        /// 5.在走迷宫时,需要确定一个策略(方法)下->右->上->左,如果该点走不通,再回溯
        /// </summary>
        /// <param name="map"></param>
        /// <param name="i">从哪个位置开始找</param>
        /// <param name="j">从哪个位置开始找</param>
        /// <returns>找到通路true,否则false</returns>
        public bool SetWay(int[,] map,int i ,int j) 
        {
            if (map[6,5] == 2)
            {
                return true;
            }
            else
            {
                //0可以走还没有走
                if (map[i,j] == 0)
                {
                    //递归回溯
                    map[i,j] = 2;
                    //下
                    if (SetWay(map, i + 1, j))
                    {
                        return true;
                    }
                    //右
                    else if (SetWay(map, i, j + 1))
                    {
                        return true;
                    }
                    //上
                    else if (SetWay(map, i - 1, j))
                    {
                        return true;
                    }
                    //左
                    else if (SetWay(map, i, j - 1))
                    {
                        return true;
                    }
                    //走不通
                    else
                    {
                        map[i,j] = 3;
                        return false;
                    }
                }
                else 
                {
                    //如果[i][j] != 0
                    //则值为 1,2,3
                    return false;
                }
            }
        }
    }

应用

代码语言:javascript
复制
static void Main(string[] args)
        {
            //地图
            int[,] map = new int[8, 7];

            //初始化墙壁
            //上下全部为1,不可走
            for (int i = 0; i < 7; i++)
            {
                map[0, i] = 1;
                map[7, i] = 1;
            }
            //左右两个边为1,不可走
            for (int i = 0; i < 8; i++)
            {
                map[i, 0] = 1;
                map[i, 6] = 1;
            }

            //设置挡板
            map[3, 1] = 1;
            map[3, 2] = 1;

            Maze maze = new Maze();
            maze.Print(map);
            maze.SetWay(map,1,1);
            maze.Print(map);
            Console.Read();
        }
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-05-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 JusterZhu 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 概要
相关产品与服务
腾讯云服务器利旧
云服务器(Cloud Virtual Machine,CVM)提供安全可靠的弹性计算服务。 您可以实时扩展或缩减计算资源,适应变化的业务需求,并只需按实际使用的资源计费。使用 CVM 可以极大降低您的软硬件采购成本,简化 IT 运维工作。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档