C#,老鼠迷宫问题的回溯法求解(Rat in a Maze)算法与源代码

news/2024/4/21 12:21:15/文章来源:https://blog.csdn.net/beijinghorn/article/details/124898445

1 老鼠迷宫问题

迷宫中的老鼠,作为另一个可以使用回溯解决的示例问题。

迷宫以块的N×N二进制矩阵给出,其中源块是最左上方的块,即迷宫[0][0],目标块是最右下方的块,即迷宫[N-1][N-1]。老鼠从源头开始,必须到达目的地。老鼠只能朝两个方向移动:向前和向下。

在迷宫矩阵中,0表示该块是死胡同,1表示该块可用于从源到目标的路径。请注意,这是典型迷宫问题的简单版本。例如,更复杂的版本可以是rat可以在4个方向上移动,而更复杂的版本可以具有有限的移动次数。

2 老鼠迷宫问题的回溯法求解

(1)创建一个解决方案矩阵,最初用0填充。

(2)创建一个递归函数,该函数采用初始矩阵、输出矩阵和rat(i,j)的位置。

(3)如果位置超出矩阵或位置无效,则返回。

(4)将位置输出[i][j]标记为1,并检查当前位置是否为目标位置。如果到达目的地,打印输出矩阵并返回。

(5)递归调用位置(i+1,j)和(i,j+1)。

(6)取消标记位置(i,j),即输出[i][j]=0。

3 源程序

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

namespace Legalsoft.Truffer.Algorithm
{
    public static class Rat_In_Maze_Problem
    {
        private static bool Rate_In_Maze_IsSafe(int[,] maze, int x, int y)
        {
            int N = maze.GetLength(0);
            return (x >= 0 && x < N && y >= 0 && y < N && maze[x, y] == 1);
        }

        public static bool Rate_In_Maze_Solve(int[,] maze, out int[,] sol)
        {
            int N = maze.GetLength(0);
            sol = new int[N, N];
            if (Rate_In_Maze_Utility(maze, 0, 0,ref sol) == false)
            {
                return false;
            }
            return true;
        }

        private static bool Rate_In_Maze_Utility(int[,] maze, int x, int y,ref int[,] sol)
        {
            int N = maze.GetLength(0);
            if (x == N - 1 && y == N - 1 && maze[x, y] == 1)
            {
                sol[x, y] = 1;
                return true;
            }

            if (Rate_In_Maze_IsSafe(maze, x, y))
            {
                if (sol[x, y] == 1)
                {
                    return false;
                }
                sol[x, y] = 1;
                if (Rate_In_Maze_Utility(maze, x + 1, y,ref sol))
                {
                    return true;
                }
                if (Rate_In_Maze_Utility(maze, x, y + 1,ref sol))
                {
                    return true;
                }
                if (Rate_In_Maze_Utility(maze, x - 1, y,ref sol))
                {
                    return true;
                }
                if (Rate_In_Maze_Utility(maze, x, y - 1,ref sol))
                {
                    return true;
                }
                sol[x, y] = 0;
                return false;
            }
            return false;
        }
    }
}
 

4 源代码

using System;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public static class Rat_In_Maze_Problem{private static bool Rate_In_Maze_IsSafe(int[,] maze, int x, int y){int N = maze.GetLength(0);return (x >= 0 && x < N && y >= 0 && y < N && maze[x, y] == 1);}public static bool Rate_In_Maze_Solve(int[,] maze, out int[,] sol){int N = maze.GetLength(0);sol = new int[N, N];if (Rate_In_Maze_Utility(maze, 0, 0,ref sol) == false){return false;}return true;}private static bool Rate_In_Maze_Utility(int[,] maze, int x, int y,ref int[,] sol){int N = maze.GetLength(0);if (x == N - 1 && y == N - 1 && maze[x, y] == 1){sol[x, y] = 1;return true;}if (Rate_In_Maze_IsSafe(maze, x, y)){if (sol[x, y] == 1){return false;}sol[x, y] = 1;if (Rate_In_Maze_Utility(maze, x + 1, y,ref sol)){return true;}if (Rate_In_Maze_Utility(maze, x, y + 1,ref sol)){return true;}if (Rate_In_Maze_Utility(maze, x - 1, y,ref sol)){return true;}if (Rate_In_Maze_Utility(maze, x, y - 1,ref sol)){return true;}sol[x, y] = 0;return false;}return false;}}
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_999199.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Docker安装主从数据库

我自己的主数据库名字 user_muster 密码是123456 从数据库 就是slave1 名字是root 密码是123456 首先开启docker后直接执行命令 docker run -d \ -p 3307:3306 \ -v /xk857/mysql/master/conf:/etc/mysql/conf.d \ -v /xk857/mysql/master/data:/var/lib/mysql \ -e MYSQL_R…

JavaWeb笔记 --- 一JDBC

一、JDBC JDBC就是Java操作关系型数据库的一种API DriverManager 注册驱动可以不写 Class.forName("com.mysql.jdbc.Driver"); Connection Statement ResultSet PrepareStatement 密码输入一个SQL脚本&#xff0c;直接登录 预编译开启在url中 数据库连接池

鸿蒙Harmony应用开发—ArkTS声明式开发(基础手势:ImageAnimator)

提供帧动画组件来实现逐帧播放图片的能力&#xff0c;可以配置需要播放的图片列表&#xff0c;每张图片可以配置时长。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 无 接口 ImageAni…

GO语言接入支付宝

GO语言接入支付宝 今天就go语言接入支付宝写一个教程 使用如下库&#xff0c;各种接口较为齐全 "github.com/smartwalle/alipay/v3"先简单介绍下加密&#xff1a; 试想&#xff0c;当用户向支付宝付款时&#xff0c;若不进行任何加密&#xff0c;那么黑客就可以任…

C++:模版进阶 | Priority_queue的模拟实现

创作不易&#xff0c;感谢三连支持 一、非类型模版参数 模板参数分类为类型形参与非类型形参。 类型形参即&#xff1a;出现在模板参数列表中&#xff0c;跟在class或者typename之类的参数类型名称。 非类型形参&#xff0c;就是用一个常量作为类(函数)模板的一个参数&…

智能音箱技术解析

目录 前言智能音箱执行步骤解析1.1 探测唤醒词或触发词1.2 语音识别1.3 意图识别1.4 执行指令 2 典型的智能音箱2.1 百度小度音响2.2 小米小爱同学2.3 苹果 HomePod 3 功能应用举例3.1 设置计时器3.2 播放音乐 结语 前言 智能音箱已经成为日常生活中不可或缺的一部分&#xff…

解决方案|珈和科技推出农业特色产业数字化服务平台

今年中央一号文件提出&#xff0c;鼓励各地因地制宜大力发展特色产业&#xff0c;支持打造乡土特色品牌。 然而&#xff0c;农业特色产业的生产、加工和销售仍然面临诸多挑战。产品优质不能优价&#xff0c;优质不能优用的现象屡见不鲜&#xff0c;产业化程度低、生产附加值不…

【SpringMVC】快速体验 SpringMVC接收数据 第一期

文章目录 一、SpringMVC 介绍1.1 主要作用1.2 核心组件和调用流程理解 二、快速体验三、SpringMVC接收数据3.1 访问路径设置3.1.1 精准路径匹配3.1.2 模糊路径匹配3.1.3 类和方法级别区别3.1.4 附带请求方式限制3.1.5 进阶注解 与 常见配置问题 3.2 接收参数&#xff08;重点&a…

mxxWechatBot微信机器人说明

大家伙&#xff0c;我是雄雄&#xff0c;欢迎关注微信公众号&#xff1a;雄雄的小课堂。 免责声明&#xff1a;该工具仅供学习使用&#xff0c;禁止使用该工具从事违法活动&#xff0c;否则永久拉黑封禁账号&#xff01;&#xff01;&#xff01;本人不对任何工具的使用负责&am…

粘包与拆包

优质博文&#xff1a;IT-BLOG-CN 一、粘包出现的原因 服务端与客户端没有约定好要使用的数据结构。Socket Client实际是将数据包发送到一个缓存buffer中&#xff0c;通过buffer刷到数据链路层。因服务端接收数据包时&#xff0c;不能断定数据包1何时结束&#xff0c;就有可能出…

吴恩达deeplearning.ai:机器学习的开发过程与优化方法

以下内容有任何不理解可以翻看我之前的博客哦&#xff1a;吴恩达deeplearning.ai专栏 我想在接下来分析下开发机器学习系统的过程&#xff0c;这样当你自己动手时&#xff0c;能够做出更加正确的判断。 机器学习开发的迭代 Iterative loop of ML development 决定模型架构 第…

酷开科技以酷开系统为媒介,打造欢乐生活场景

家人相聚在一起的时光总是那么美好&#xff0c;在欢聚的日子里&#xff0c;我们也总是希望能够让时间变得慢一点&#xff0c;再慢一点&#xff0c;但是随着春节假期的结束&#xff0c;很多人已经开始了新一年的忙碌&#xff0c;大家纷纷回到工作、学习岗位&#xff0c;回归之前…

GBU1510-ASEMI逆变器整流桥GBU1510

编辑&#xff1a;ll GBU1510-ASEMI逆变器整流桥GBU1510 型号&#xff1a;GBU1510 品牌&#xff1a;ASEMI 封装&#xff1a;GBU-4 最大重复峰值反向电压&#xff1a;1000V 最大正向平均整流电流(Vdss)&#xff1a;15A 功率(Pd)&#xff1a;大功率 芯片个数&#xff1a;4…

Java后端核心——Servlet

目录 一.概述 二.基础实现 1.导入坐标 2.定义实现类 3.注解 4.访问Servlet 三.执行流程 四.生命周期 1.加载和实例化 2.初始化 3.请求处理 4.服务终止 五.方法 1.init 2.service 3.destroy 4.getServletInfo 5.getServletConfig 六.体系结构 七.urlPatter…

基于YOLOv8深度学习的智能道路裂缝检测与分析系统【python源码+Pyqt5界面+数据集+训练代码】深度学习实战、目标检测、目标分割

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…

Rollup Summer:一览 Rollup 生态全景图

作者&#xff1a;Stanley&#xff0c;Kernel Ventures 编译&#xff1a;JIN&#xff0c;Techub News 短短几天内&#xff0c;ZKFair 的总锁定价值&#xff08;TVL&#xff09;已达到 1.2 亿美元&#xff0c;目前稳定在 8000 万美元&#xff0c;使其成为增长最快的 Rollup 之一…

测试常用MySQL相关

1、通过命令行连接数据库 [rootlocalhost ~]# mysql -u root -p Enter password: 输入以上命令&#xff0c;回车后输入密码&#xff0c;回车&#xff0c;出现 mysql> 命令提示窗口则表示登录成功&#xff0c;可以在mysql>下输入任何sql语句。 2、退出mysql mysql>…

【Python】新手入门:什么是变量?如何在Python中声明变量?变量有哪些使用方式?

【Python】新手入门&#xff1a;什么是变量&#xff1f;如何在Python中声明变量&#xff1f;变量有哪些使用方式&#xff1f; &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【…

C# OpenCvSharp DNN FreeYOLO 密集行人检测

目录 效果 模型信息 项目 代码 下载 C# OpenCvSharp DNN FreeYOLO 密集行人检测 效果 模型信息 Inputs ------------------------- name&#xff1a;input tensor&#xff1a;Float[1, 3, 192, 320] --------------------------------------------------------------- …

#stm32外设总结电容触摸按键

BS8116A-3 IRQ 外部中断请求 NMOS输出内部上拉 SCL SDA IIC通信接口 VDD 供电电压2.2-5.5V Ct电容: 0~25 pF 电容越大灵敏度越低 1、 软件使用流程 初始化 将IIC的两个引脚初始化为复用开漏模式 按键引脚设置上拉输入 下降沿触发外部中断 void KEY_Init(void) {//uint8_t …