路径之谜 蓝桥杯 89
题目描述
小明冒充 X 星球的骑士,进入了一个奇怪的城堡。
城堡里边什么都没有,只有方形石头铺成的地面。
假设城堡地面是 n×n 个方格。如下图所示。

按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着走,也不能跳跃。每走到一个新方格,就要向正北方和正西方各射一箭。(城堡的西墙和北墙内各有 n 个靶子)同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目,你能推断出骑士的行走路线吗?有时是可以的,比如上图中的例子。
本题的要求就是已知箭靶数字,求骑士的行走路径(测试数据保证路径唯一)
输入描述
第一行一个整数 N (0≤≤200≤N≤20),表示地面有 N×N 个方格。
第二行 N 个整数,空格分开,表示北边的箭靶上的数字(自西向东)
第三行 N 个整数,空格分开,表示西边的箭靶上的数字(自北向南)
输出描述
输出一行若干个整数,表示骑士路径。
为了方便表示,我们约定每个小格子用一个数字代表,从西北角开始编号: 0,1,2,3 ⋯⋯
比如,上图中的方块编号为:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
输入输出样例
示例
输入
4
2 4 3 4
4 3 3 3输出
0 4 5 1 2 3 7 11 10 9 13 14 15dfs搜索,区别是多了一个栈来记录路径
def dfs(x,y):if a[x]<0 or b[y]<0:#步数已经用完return if x==n-1 and y==n-1:#到最后一格jieshu =1for i in range(n):if a[i]!=0 or b[i]!=0:#不满足条件跳出jieshu = 0returnif jieshu==1:#满足条件,输出路径for i in range(len(path)):print(path[i],end=' ')for d in [(1,0),(-1,0),(0,1),(0,-1)]:tx ,ty= x+d[0],y+d[1]if 0<= tx <n and 0<=ty<n and vis[tx][ty]==0:vis[tx][ty]=1path.append(tx*n+ty)#每一个格子的算法 因为起点是[0][0],所以每个格子的数字是tx*n+tya[tx]-=1b[ty]-=1dfs(tx,ty)path.pop()#恢复a[tx]+=1b[ty]+=1vis[tx][ty]=0
n=int(input())
vis = [[0]*n for i in range(n)]
path = []
path.append(0)
b = list(map(int,input().split()))
a = list(map(int,input().split()))
vis[0][0]=1#标记第一个格子
a[0]-=1#给第一行和第一列的计数减一
b[0]-=1
dfs(0,0)
相关文章:
路径之谜 蓝桥杯 89
题目描述小明冒充 X 星球的骑士,进入了一个奇怪的城堡。城堡里边什么都没有,只有方形石头铺成的地面。假设城堡地面是 nn 个方格。如下图所示。按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着走,也不…...
Mysql数据库如何调优
MYSQL数据库调优 索引 1、对于常用的查询字段加索引,但如果常用字段只有几个常量值就不需要加索引,或者使用索引会失效的情况; 2、索引失效的情况: 1、索引列使用函数,计算(加减乘除等) …...
CAN(FD)记录仪在新能源汽车整车控制器(VCU)、电池管理系统(BMS)、电机控制器(MCU)、发动机ECU中的应用,免去出差烦恼
今天介绍CAN(FD)记录仪在新能源汽车整车控制器(VCU)、电池管理系统(BMS)、电机控制器(MCU)、发动机ECU中的应用 第一步:新能源汽车整车控制器(VCU)先供上电,…...
【设计模式】23种设计模式之七大原则
【设计模式】23种设计模式之七大原则什么是设计模式的原则1、单一职责原则基本介绍案例分析注意事项2、接口隔离原则基本介绍案例分析代码实现3、依赖倒转原则基本介绍案例分析依赖传递的三种方式注意事项4、里氏替换原则关于继承性的思考和说明基本介绍案例分析5、开闭原则ocp…...
python - 文件操作
1. 概念 计算机内存通常分为两种类型:主存储器和辅助存储器。 主存储器是计算机中最重要的存储器类型之一。它是计算机中用于存储正在运行的程序和数据的存储器。主存储器通常是易失性的,这意味着当计算机关闭时,其中存储的数据将被删除。主存…...
docker打包golang应用
一、错误的打包方式在本地环境编译,然后将可执行程序放入 alpine(docker.io/alpine:latest)准备web程序package mainimport ("fmt""net/http" )func main() {server : &http.Server{Addr: ":8888",}http.HandleFunc("/"…...
redis 内容总结
目录redis 内容列举Redis和Memcached比较Redis简介1、Redis 数据结构2、Redis的持久化机制3、Redis 内容管理(淘汰策略/删除策略)4、Redis 事务5、Redis 缓存三大问题6、Redis 集群7、Redis 应用redis 内容列举 官网:https://redis.io/ 中文…...
贪心算法(一)
一、概念 贪心算法的核心思想是,在处理一个大问题时,划分为多个局部并在每个局部选择最优解,并且认为在每个局部选择最优解,那么最后全局的问题得到的就是最优解。 贪心算法可以解决一些问题,但是不适用于所有问题&a…...
【栈和队列OJ题】有效的括号用队列实现栈用栈实现队列设计循环队列
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯长路漫漫浩浩,万事皆有期待 文章目录OJ题1.有效的括号1.1…...
kuernetes 资源对象分析报错
文章目录1. pod 状态1.1 容器启动错误类型1.2 ImagePullBackOff 错误1.3 CrashLoopBackOff1.4 Pending2. Service 连接状态3. Ingress 连接状态1. pod 状态 创建一个 pod-status.yaml apiVersion: v1 kind: Pod metadata:name: runninglabels:app: nginx spec:containers:- na…...
动态内存的开辟
🐶博主主页:ᰔᩚ. 一怀明月ꦿ ❤️🔥专栏系列:线性代数,C初学者入门训练,题解C,C的使用文章,「初学」C 🔥座右铭:“不要等到什么都没有了,才下…...
【蓝桥杯-筑基篇】搜索
🍓系列专栏:蓝桥杯 🍉个人主页:个人主页 目录 递归树 1.递归构建二进制串 2.全排列的 DFS 解法 3.全排列的 BFS 解法 4.数的划分法 5.图书推荐 递归树 递归树是一种用于分析递归算法时间复杂度的工具。它可以将递归算法的执行过程可视化…...
week5-质数-最大公约数-快速幂-组合计数-博弈论
蓝桥 等差数列——欧几里得算法质数质数的判定——试除法分解质因数——试除法筛质数——埃氏筛法筛质数——线性筛法质数问题质数距离约数试除法求约数约数个数约数之和最大公约数-欧几里得算法(辗转相除法)扩展欧几里得算法裴蜀定理应用——线性同余方程消灭老鼠Hankson的趣…...
CloudCompare 二次开发(6)——插件中拖拽添加Qt窗口(区域生长算法为例)
目录 一、概述二、插件制作三、Cmake编译四、插件代码五、结果展示一、概述 手动拖拽的方式搭建Qt对话框界面的制作流程,以PCL中的点云区域生长算法为例进行制作。 二、插件制作 1、将....\plugins\example路径下的ExamplePlugin复制一份并修改名字为CCPointCloudProcess。 …...
2023值得推荐的高颜值Vue3.0 Web PC端UI框架,赶紧收藏学习!
Hello,我是前端胡说,本期给大家带来2023值得推荐的Vue3.0 UI组件库,希望大家喜欢! Vue3 正式发布已经有一段时间了,2022年2月也正式变成 Vue 项目的默认版本。在过去一年多的时间里,各大组件库、框架也紧跟…...
Springboot项目Aop、拦截器、过滤器横向对比
前言伟人曾经说过,没有调查就没有发言权(好像是伟人说的,不管谁说的,这句话是正确的),有些东西看着简单,张口就来,但很有可能是错的。我个人的经验是,aop、过滤器、拦截器的实现方式很简单&…...
为了之后找工作不被虐,每天刷3道《剑指offer》Day-1
本文已收录于专栏🌻《刷题笔记》文章目录前言💖 1、二维数组中的查找题目描述思路💖 2、替换空格题目描述思路💖 3、从尾到头打印链表题目描述思路一(反转函数)思路二(递归)思路二&a…...
Linux-磁盘管理介绍
Linux-磁盘管理介绍 计算硬盘介绍 硬盘是计算机主要存储媒介之一,由一个或者多个铝制或者玻璃制的碟片组成,碟片外覆盖有铁磁性材料,硬盘内部由磁道、柱面、扇区、磁头等部件组成; cylinder:柱面sector:扇区 磁道与…...
爬虫架构(一):爬虫中的去重处理
目录一、概要二、去重应用场景以及基本原理2.1 爬虫中什么业务需要使用去重2.2 去重实现的基本原理2.3 根据原始数据进行去重判断2.4 根据原始数据的特征值进行去重判断2.5 临时去重容器与持久化去重容器2.6 常用几种特殊的原始数据特征值计算三、基于信息摘要算法的去重3.1 信…...
算法刷题总结 (二) 回溯与深广搜算法
算法总结2 回溯与深广搜算法一、理解回溯算法1.1、回溯的概念1.2、回溯法的效率1.3、回溯法问题分类1.4、回溯法的做题步骤二、经典问题2.1、组合问题2.1.1、77. 组合 - 值不重复2.1.2、216.组合总和III - 值不重复且等于目标值2.1.3、17. 电话号码的字母组合 - 双层回溯2.1.4、…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
