当前位置: 首页 > news >正文

蓝桥杯-暴力搜索BFS+DFS

九九乘法表挂毯

问题描述:

        在一个古老的城堡里,一位名为 Alex 的少年发现了一幅巨大的九九乘法表挂毯。挂毯被划分成了9x9的方格,每个方格上写着相应的乘积。Alex 想象自己站在数值为1的方格上,他的目标是到达数值为 81 的方格。然而,少年遵循着一项规则:他只能移动到数值为 1、81 或任意偶数的相邻方格上。城堡的图书管理员告诉他,只有找到最短路径到达目标,他才能解开挂毯的秘密。
        请你帮助 Alex计算,在遵循上述移动规则的情况下,他从1到81的最短路径有多少种可能。

输入格式
无。
输出格式
输出一个整数,表示从1到 81 的最短路径的可能数量。

题目分析:

        这道题深度的考验BFS和DFS的综合运用,可以作为考验自己是否对这两种算法熟悉的一道题去练练手,下方配py的题解,仅供参考。 

综合思路就是,先用BFS求出最短路径是多少,然后用DFS去求符合该步数的路径有多少条。

代码实现:

m=[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18],
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27],
[0, 4, 8, 12, 16, 20, 24, 28, 32, 36],
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45],
[0, 6, 12, 18, 24, 30, 36, 42, 48, 54],
[0, 7, 14, 21, 28, 35, 42, 49, 56, 63],
[0, 8, 16, 24, 32, 40, 48, 56, 64, 72],
[0, 9, 18, 27, 36, 45, 54, 63, 72, 81]]dirs=[[0,1],[0,-1],[-1,0],[1,0]] #四条路
def bfs(m):st,ed=[1,1],[9,9]stack=[[st,0]]while stack:curnode,step=stack.pop(0)print(curnode)if curnode==ed: return stepstep+=1for i in dirs:a0,a1=curnode[0]+i[0],curnode[1]+i[1]if 9>=a0>0 and 9>=a1>0 and (m[a0][a1] %2==0 or m[a0][a1]==81):newnode=[a0,a1]stack.append([newnode,step])m[a0][a1]=1
print(bfs(m))res=0
def dfs(x,y,key,step):global resif step>16: returnif key==81:res+=1returnelse:for dir in dirs:x0,y0=x+dir[0],y+dir[1]if 9>=x0>0 and 9>=y0>0 and (m[x0][y0]%2==0 or m[x0][y0]==81):v=m[x0][y0]dfs(x0,y0,v,step+1)
dfs(1,1,1,0)
print(res)

题目总结: 

这种题目主要考察对DFS和BFS两种搜索算法的理解和运用能力。所以要求我们必须掌握以下内容:

  1. 理解DFS和BFS的基本原理:DFS是深度优先搜索算法,从起始节点开始,沿着一条路径一直往下搜索直到无法继续为止,然后返回上一个节点继续搜索;BFS是广度优先搜索算法,从起始节点开始,先搜索所有相邻节点,再逐层向下搜索。

  2. 分析DFS和BFS的应用场景:DFS通常用于寻找所有可能的解或路径,适用于图的遍历、拓扑排序、连通性检测等问题;BFS通常用于求最短路径、最小步数等问题。

  3. 比较DFS和BFS的特点:DFS递归实现简单,但可能会无限循环;BFS借助队列实现,保证了最优解,但空间复杂度较高。

  4. 实际应用中如何选择DFS和BFS:根据具体问题特点选择合适的搜索算法,通常情况下,如果需要找到解的所有可能,可以使用DFS;如果要求最短路径或步数,可以使用BFS。

相关文章:

蓝桥杯-暴力搜索BFS+DFS

九九乘法表挂毯 问题描述: 在一个古老的城堡里,一位名为 Alex 的少年发现了一幅巨大的九九乘法表挂毯。挂毯被划分成了9x9的方格,每个方格上写着相应的乘积。Alex 想象自己站在数值为1的方格上,他的目标是到达数值为 81 的方格。…...

巧用count与count()

在C#中&#xff0c;talentInnoPfChains.Count() 和 talentInnoPfChains.Count 的性能差异主要取决于 talentInnoPfChains 的类型。这里有两种可能的情况&#xff1a; 如果 talentInnoPfChains 是一个实现了 ICollection<T> 接口的集合&#xff08;如 List<T>, Hash…...

MongoDB 覆盖索引查询:提升性能的完整指南

MongoDB 覆盖索引查询是一种优化数据库查询性能的技术&#xff0c;它通过创建适当的索引&#xff0c;使查询可以直接从索引中获取所需的数据&#xff0c;而无需访问实际的文档数据。这种方式可以减少磁盘 I/O 和内存消耗&#xff0c;提高查询性能。 基本语法 在 MongoDB 中&a…...

ECMAScript详解

ECMAScript&#xff08;简称ES&#xff09;是一种由Ecma国际&#xff08;前身为欧洲计算机制造商协会&#xff0c;European Computer Manufacturers Association&#xff09;通过ECMA-262标准化的脚本程序设计语言。以下是对ECMAScript的详细说明&#xff1a; 1. 定义与起源 …...

如何在Windows 10上对硬盘进行碎片整理?这里提供步骤

随着时间的推移&#xff0c;由于文件系统中的碎片&#xff0c;硬盘驱动器可能会开始以较低的效率运行。为了加快驱动器的速度&#xff0c;你可以使用内置工具在Windows 10中对其进行碎片整理和优化。方法如下。 什么是碎片整理 随着时间的推移&#xff0c;组成文件的数据块&a…...

科学高效备考AMC8和AMC10竞赛,吃透2000-2024年1850道真题和解析

多做真题&#xff0c;吃透真题和背后的知识点是备考AMC8、AMC10有效的方法之一&#xff0c;通过做真题&#xff0c;可以帮助孩子找到真实竞赛的感觉&#xff0c;而且更加贴近比赛的内容&#xff0c;可以通过真题查漏补缺&#xff0c;更有针对性的补齐知识的短板。 今天我们继续…...

SQL——SELECT相关的题目

目录 197、上升的温度 577、员工奖金 586、订单最多的客户 596、超过5名学生的课 610、判断三角形 620、有趣的电影 181、超过经理收入的员工 1179、重新格式化部门表&#xff08;行转列&#xff09; 1280、学生参加各科测试的次数 1068、产品销售分析I 1075、项目员工I …...

etcd集群部署

1.etcd介绍 1.1 什么是etcd etcd的官方定义如下: A distributed, reliable key-value store for the most critical data of distributed systemetcd是一个Go语言编写的分布式、高可用的一致性键值存储系统,用于提供可靠的分布式键值(key value)存储、配置共享和服务发现等…...

VBA_MF系列技术资料1-615

MF系列VBA技术资料1-615 为了让广大学员在VBA编程中有切实可行的思路及有效的提高自己的编程技巧&#xff0c;我参考大量的资料&#xff0c;并结合自己的经验总结了这份MF系列VBA技术综合资料&#xff0c;而且开放源码&#xff08;MF04除外&#xff09;&#xff0c;其中MF01-0…...

常用激活函数学习

常用激活函数及其应用 ReLU (Rectified Linear Unit) 公式: f ( x ) max ⁡ ( 0 , x ) f(x) \max(0, x) f(x)max(0,x)理解: 当输入值为正时&#xff0c;输出等于输入值&#xff1b;否则输出为0。ReLU函数简单且计算效率高&#xff0c;能有效缓解梯度消失问题&#xff0c;促进…...

html中被忽略的简单标签

1&#xff1a; alt的作用是在图片不能显示时的提示信息 <img src"https://img.xunfei.cn/mall/dev/ifly-mall-vip- service/business/vip/common/202404071019208761.jp" alt"提示信息" width"100px" height"100px" /> 2&#…...

Vue.Draggable:强大的Vue拖放组件技术探索

一、引言 随着前端技术的不断发展&#xff0c;拖放&#xff08;Drag-and-Drop&#xff09;功能已经成为许多Web应用不可或缺的一部分。Vue.js作为现代前端框架的佼佼者&#xff0c;为开发者提供了丰富的生态系统和强大的工具链。Vue.Draggable作为基于Sortable.js的Vue拖放组件…...

linux mail命令及其历史

一、【问题描述】 最近隔壁组有人把crontab删了&#xff0c;crontab这个命令有点反人类&#xff0c;它的参数特别容易误操作&#xff1a; crontab - 是删除计划表 crontab -e 是编辑&#xff0c;总之就是特别容易输入错误。 好在可以通过mail命令找回&#xff0c;但是mai…...

数据驱动(Data-Driven)和以数据为中心(Data-Centric)的区别

一、什么是数据驱动&#xff1f; 数据驱动&#xff08;Data-Driven&#xff09;是在管理科学领域经常提到的名词。数据驱动决策&#xff08;Data-Driven Decision Making&#xff0c;简称DDD&#xff09;是一种方法论&#xff0c;即在决策过程中主要依赖于数据分析和解释&…...

aosp14的分屏接口ISplitScreen接口获取方式更新-学员疑问答疑

背景&#xff1a; 有学员朋友在学习马哥的分屏pip自由窗口专题时候&#xff0c;做相关分屏做小桌面项目时候&#xff0c;因为原来课程版本是基于android 13进行的讲解的&#xff0c;但是现在公司已经开始逐渐进行相关的android 14的适配了&#xff0c;但是android 14这块相比a…...

定积分求解过程是否变限问题 以及当换元时注意事项

目录 定积分求解过程是否变限问题 文字理解&#xff1a; 实例理解&#xff1a; 易错点和易混点&#xff1a; 1&#xff1a;定积分中的换元指什么&#xff1f; 2&#xff1a; 不定积分中第一类换元法和第二类换元法的本质和区别 3&#xff1a; df(x) ----> df(x)这…...

保研机试算法训练个人记录笔记(七)

输入格式&#xff1a; 在第1 行给出不超过10^5 的正整数N, 即参赛&#xff5d;人数。随后N 行&#xff0c;每行给出一位参赛者的 信息和成绩&#xff0c;包括其所代表的学校的编号&#xff08;从1 开始连续编号&#xff09;及其比赛成绩&#xff08;百分制&#xff09;&#xf…...

【MySQL精通之路】SQL优化(1)-查询优化(23)-避免全表扫描

当MySQL使用全表扫描来解析查询时&#xff0c;EXPLAIN的输出在type列中显示ALL。 这种情况通常发生在以下情况下&#xff1a; 该表非常小&#xff0c;因此执行全表扫描比查找关键字更快。这对于少于10行且行长较短的表来说很常见。 对于索引列&#xff0c;ON或WHERE子句中没有…...

【Linux】写时拷贝技术COW (copy-on-write)

文章目录 Linux写时拷贝技术(copy-on-write)进程的概念进程的定义进程和程序的区别PCB的内部构成 程序是如何被加载变成进程的&#xff1f;写时复制&#xff08;Copy-On-Write, COW&#xff09;写时复制机制的原理写时拷贝的场景 fork与COWvfork与fork Linux写时拷贝技术(copy-…...

用python使用主成分分析数据

import pandas as pd #导入处理二维表格的库 import numpy as np #导入数值计算的库 from sklearn.preprocessing import StandardScaler #导入数据标准化模块 import matplotlib.pyplot as plt #导入画图的包 from sklearn.decomposition import PCA #导入主成…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...