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

路径之谜 蓝桥杯 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 15

dfs搜索,区别是多了一个栈来记录路径

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 星球的骑士&#xff0c;进入了一个奇怪的城堡。城堡里边什么都没有&#xff0c;只有方形石头铺成的地面。假设城堡地面是 nn 个方格。如下图所示。按习俗&#xff0c;骑士要从西北角走到东南角。可以横向或纵向移动&#xff0c;但不能斜着走&#xff0c;也不…...

Mysql数据库如何调优

MYSQL数据库调优 索引 1、对于常用的查询字段加索引&#xff0c;但如果常用字段只有几个常量值就不需要加索引&#xff0c;或者使用索引会失效的情况&#xff1b; 2、索引失效的情况&#xff1a; ​ 1、索引列使用函数&#xff0c;计算&#xff08;加减乘除等&#xff09; …...

CAN(FD)记录仪在新能源汽车整车控制器(VCU)、电池管理系统(BMS)、电机控制器(MCU)、发动机ECU中的应用,免去出差烦恼

今天介绍CAN(FD)记录仪在新能源汽车整车控制器&#xff08;VCU&#xff09;、电池管理系统&#xff08;BMS&#xff09;、电机控制器&#xff08;MCU&#xff09;、发动机ECU中的应用 第一步&#xff1a;新能源汽车整车控制器&#xff08;VCU&#xff09;先供上电&#xff0c…...

【设计模式】23种设计模式之七大原则

【设计模式】23种设计模式之七大原则什么是设计模式的原则1、单一职责原则基本介绍案例分析注意事项2、接口隔离原则基本介绍案例分析代码实现3、依赖倒转原则基本介绍案例分析依赖传递的三种方式注意事项4、里氏替换原则关于继承性的思考和说明基本介绍案例分析5、开闭原则ocp…...

python - 文件操作

1. 概念 计算机内存通常分为两种类型&#xff1a;主存储器和辅助存储器。 主存储器是计算机中最重要的存储器类型之一。它是计算机中用于存储正在运行的程序和数据的存储器。主存储器通常是易失性的&#xff0c;这意味着当计算机关闭时&#xff0c;其中存储的数据将被删除。主存…...

docker打包golang应用

一、错误的打包方式在本地环境编译&#xff0c;然后将可执行程序放入 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 内容管理&#xff08;淘汰策略/删除策略&#xff09;4、Redis 事务5、Redis 缓存三大问题6、Redis 集群7、Redis 应用redis 内容列举 官网&#xff1a;https://redis.io/ 中文…...

贪心算法(一)

一、概念 贪心算法的核心思想是&#xff0c;在处理一个大问题时&#xff0c;划分为多个局部并在每个局部选择最优解&#xff0c;并且认为在每个局部选择最优解&#xff0c;那么最后全局的问题得到的就是最优解。 贪心算法可以解决一些问题&#xff0c;但是不适用于所有问题&a…...

【栈和队列OJ题】有效的括号用队列实现栈用栈实现队列设计循环队列

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录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…...

动态内存的开辟

&#x1f436;博主主页&#xff1a;ᰔᩚ. 一怀明月ꦿ ❤️‍&#x1f525;专栏系列&#xff1a;线性代数&#xff0c;C初学者入门训练&#xff0c;题解C&#xff0c;C的使用文章&#xff0c;「初学」C &#x1f525;座右铭&#xff1a;“不要等到什么都没有了&#xff0c;才下…...

【蓝桥杯-筑基篇】搜索

&#x1f353;系列专栏:蓝桥杯 &#x1f349;个人主页:个人主页 目录 递归树 1.递归构建二进制串 2.全排列的 DFS 解法 3.全排列的 BFS 解法 4.数的划分法 5.图书推荐 递归树 递归树是一种用于分析递归算法时间复杂度的工具。它可以将递归算法的执行过程可视化&#xf…...

week5-质数-最大公约数-快速幂-组合计数-博弈论

蓝桥 等差数列——欧几里得算法质数质数的判定——试除法分解质因数——试除法筛质数——埃氏筛法筛质数——线性筛法质数问题质数距离约数试除法求约数约数个数约数之和最大公约数-欧几里得算法(辗转相除法)扩展欧几里得算法裴蜀定理应用——线性同余方程消灭老鼠Hankson的趣…...

CloudCompare 二次开发(6)——插件中拖拽添加Qt窗口(区域生长算法为例)

目录 一、概述二、插件制作三、Cmake编译四、插件代码五、结果展示一、概述 手动拖拽的方式搭建Qt对话框界面的制作流程,以PCL中的点云区域生长算法为例进行制作。 二、插件制作 1、将....\plugins\example路径下的ExamplePlugin复制一份并修改名字为CCPointCloudProcess。 …...

2023值得推荐的高颜值Vue3.0 Web PC端UI框架,赶紧收藏学习!

Hello&#xff0c;我是前端胡说&#xff0c;本期给大家带来2023值得推荐的Vue3.0 UI组件库&#xff0c;希望大家喜欢&#xff01; Vue3 正式发布已经有一段时间了&#xff0c;2022年2月也正式变成 Vue 项目的默认版本。在过去一年多的时间里&#xff0c;各大组件库、框架也紧跟…...

Springboot项目Aop、拦截器、过滤器横向对比

前言伟人曾经说过&#xff0c;没有调查就没有发言权(好像是伟人说的&#xff0c;不管谁说的&#xff0c;这句话是正确的)&#xff0c;有些东西看着简单&#xff0c;张口就来&#xff0c;但很有可能是错的。我个人的经验是&#xff0c;aop、过滤器、拦截器的实现方式很简单&…...

为了之后找工作不被虐,每天刷3道《剑指offer》Day-1

本文已收录于专栏&#x1f33b;《刷题笔记》文章目录前言&#x1f496; 1、二维数组中的查找题目描述思路&#x1f496; 2、替换空格题目描述思路&#x1f496; 3、从尾到头打印链表题目描述思路一&#xff08;反转函数&#xff09;思路二&#xff08;递归&#xff09;思路二&a…...

Linux-磁盘管理介绍

Linux-磁盘管理介绍 计算硬盘介绍 硬盘是计算机主要存储媒介之一&#xff0c;由一个或者多个铝制或者玻璃制的碟片组成&#xff0c;碟片外覆盖有铁磁性材料&#xff0c;硬盘内部由磁道、柱面、扇区、磁头等部件组成; cylinder&#xff1a;柱面sector&#xff1a;扇区 磁道与…...

爬虫架构(一):爬虫中的去重处理

目录一、概要二、去重应用场景以及基本原理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、…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...