蓝桥杯-暴力搜索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两种搜索算法的理解和运用能力。所以要求我们必须掌握以下内容:
-
理解DFS和BFS的基本原理:DFS是深度优先搜索算法,从起始节点开始,沿着一条路径一直往下搜索直到无法继续为止,然后返回上一个节点继续搜索;BFS是广度优先搜索算法,从起始节点开始,先搜索所有相邻节点,再逐层向下搜索。
-
分析DFS和BFS的应用场景:DFS通常用于寻找所有可能的解或路径,适用于图的遍历、拓扑排序、连通性检测等问题;BFS通常用于求最短路径、最小步数等问题。
-
比较DFS和BFS的特点:DFS递归实现简单,但可能会无限循环;BFS借助队列实现,保证了最优解,但空间复杂度较高。
-
实际应用中如何选择DFS和BFS:根据具体问题特点选择合适的搜索算法,通常情况下,如果需要找到解的所有可能,可以使用DFS;如果要求最短路径或步数,可以使用BFS。
相关文章:
蓝桥杯-暴力搜索BFS+DFS
九九乘法表挂毯 问题描述: 在一个古老的城堡里,一位名为 Alex 的少年发现了一幅巨大的九九乘法表挂毯。挂毯被划分成了9x9的方格,每个方格上写着相应的乘积。Alex 想象自己站在数值为1的方格上,他的目标是到达数值为 81 的方格。…...
巧用count与count()
在C#中,talentInnoPfChains.Count() 和 talentInnoPfChains.Count 的性能差异主要取决于 talentInnoPfChains 的类型。这里有两种可能的情况: 如果 talentInnoPfChains 是一个实现了 ICollection<T> 接口的集合(如 List<T>, Hash…...
MongoDB 覆盖索引查询:提升性能的完整指南
MongoDB 覆盖索引查询是一种优化数据库查询性能的技术,它通过创建适当的索引,使查询可以直接从索引中获取所需的数据,而无需访问实际的文档数据。这种方式可以减少磁盘 I/O 和内存消耗,提高查询性能。 基本语法 在 MongoDB 中&a…...
ECMAScript详解
ECMAScript(简称ES)是一种由Ecma国际(前身为欧洲计算机制造商协会,European Computer Manufacturers Association)通过ECMA-262标准化的脚本程序设计语言。以下是对ECMAScript的详细说明: 1. 定义与起源 …...

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

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

SQL——SELECT相关的题目
目录 197、上升的温度 577、员工奖金 586、订单最多的客户 596、超过5名学生的课 610、判断三角形 620、有趣的电影 181、超过经理收入的员工 1179、重新格式化部门表(行转列) 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编程中有切实可行的思路及有效的提高自己的编程技巧,我参考大量的资料,并结合自己的经验总结了这份MF系列VBA技术综合资料,而且开放源码(MF04除外),其中MF01-0…...
常用激活函数学习
常用激活函数及其应用 ReLU (Rectified Linear Unit) 公式: f ( x ) max ( 0 , x ) f(x) \max(0, x) f(x)max(0,x)理解: 当输入值为正时,输出等于输入值;否则输出为0。ReLU函数简单且计算效率高,能有效缓解梯度消失问题,促进…...

html中被忽略的简单标签
1: 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拖放组件技术探索
一、引言 随着前端技术的不断发展,拖放(Drag-and-Drop)功能已经成为许多Web应用不可或缺的一部分。Vue.js作为现代前端框架的佼佼者,为开发者提供了丰富的生态系统和强大的工具链。Vue.Draggable作为基于Sortable.js的Vue拖放组件…...

linux mail命令及其历史
一、【问题描述】 最近隔壁组有人把crontab删了,crontab这个命令有点反人类,它的参数特别容易误操作: crontab - 是删除计划表 crontab -e 是编辑,总之就是特别容易输入错误。 好在可以通过mail命令找回,但是mai…...
数据驱动(Data-Driven)和以数据为中心(Data-Centric)的区别
一、什么是数据驱动? 数据驱动(Data-Driven)是在管理科学领域经常提到的名词。数据驱动决策(Data-Driven Decision Making,简称DDD)是一种方法论,即在决策过程中主要依赖于数据分析和解释&…...

aosp14的分屏接口ISplitScreen接口获取方式更新-学员疑问答疑
背景: 有学员朋友在学习马哥的分屏pip自由窗口专题时候,做相关分屏做小桌面项目时候,因为原来课程版本是基于android 13进行的讲解的,但是现在公司已经开始逐渐进行相关的android 14的适配了,但是android 14这块相比a…...
定积分求解过程是否变限问题 以及当换元时注意事项
目录 定积分求解过程是否变限问题 文字理解: 实例理解: 易错点和易混点: 1:定积分中的换元指什么? 2: 不定积分中第一类换元法和第二类换元法的本质和区别 3: df(x) ----> df(x)这…...
保研机试算法训练个人记录笔记(七)
输入格式: 在第1 行给出不超过10^5 的正整数N, 即参赛}人数。随后N 行,每行给出一位参赛者的 信息和成绩,包括其所代表的学校的编号(从1 开始连续编号)及其比赛成绩(百分制)…...
【MySQL精通之路】SQL优化(1)-查询优化(23)-避免全表扫描
当MySQL使用全表扫描来解析查询时,EXPLAIN的输出在type列中显示ALL。 这种情况通常发生在以下情况下: 该表非常小,因此执行全表扫描比查找关键字更快。这对于少于10行且行长较短的表来说很常见。 对于索引列,ON或WHERE子句中没有…...

【Linux】写时拷贝技术COW (copy-on-write)
文章目录 Linux写时拷贝技术(copy-on-write)进程的概念进程的定义进程和程序的区别PCB的内部构成 程序是如何被加载变成进程的?写时复制(Copy-On-Write, COW)写时复制机制的原理写时拷贝的场景 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智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...

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

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

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

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

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

三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...