路径之谜 蓝桥杯 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、…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
