Python:路径之谜(DFS剪枝)
题目描述
小张冒充 X 星球的骑士,进入了一个奇怪的城堡。
城堡里边什么都没有,只有方形石头铺成的地面。
假设城堡地面是 n×n 个方格。如下图所示。
按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着走,也不能跳跃。每走到一个新方格,就要向正北方和正西方各射一箭。(城堡的西墙和北墙内各有 n 个靶子)同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目,你能推断出骑士的行走路线吗?有时是可以的,比如上图中的例子。
本题的要求就是已知箭靶数字,求骑士的行走路径(测试数据保证路径唯一)
输入描述
第一行一个整数 N (0≤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:题目要求输出一条路径,用DFS很合适,DFS搜索过程中,自然生成一条路径。
剪枝:每走到一个格子,对应的靶子上箭多一支,靶子上的箭等于给定的数字后,就不用再DFS下去了。(或者做减法,靶子的数字减到0)
记录路径的技巧:根据题目的要求,用栈来跟踪DFS的过程,记录DFS走过的路径,是最方便的。DFS到某个格子时,把这个格子放到栈里,表示路径增加了这个格子。DFS回溯的时候,退出了这个格子,表示路径上不再包括这个格子,需要从栈中弹走这个格子。
参考代码:
def dfs(x,y):if a[x]<0 or b[y]<0:#先开头检验是否符合标准returnif x==n-1 and y==n-1:#走到终点flag=1for i in range(n): #检查每个箭靶上的数字是否减尽if a[i]!=0 or b[i]!=0:flag=0returnif flag==1:for i in range(len(path)):print(path[i],end=' ')l=[(1,0),(-1,0),(0,-1),(0,1)] for i in range(4):xt=x+l[i][0]yt=y+l[i][1]if 0<=xt<n and 0<=yt<n and vis[xt][yt]==0:vis[xt][yt]=1 #标记现场path.append(xt*n+yt) #这个是坐标的计算方法a[xt]-=1; b[yt]-=1dfs(xt,yt) path.pop() a[xt]+=1; b[yt]+=1 #还原现场vis[xt][yt]=0n=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)
相关文章:

Python:路径之谜(DFS剪枝)
题目描述 小张冒充 X 星球的骑士,进入了一个奇怪的城堡。 城堡里边什么都没有,只有方形石头铺成的地面。 假设城堡地面是 nn 个方格。如下图所示。 按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着走…...

阿里巴巴在开源压测工具 JMeter 上的实践和优化
Apache JMeter [1] 是 Apach 旗下的开源压测工具,创建于 1999 年初,迄今已有超过 20 年历史。JMeter 功能丰富,社区(用户群体)庞大,是主流开源压测工具之一。 性能测试通常集中在新系统上线或大型活动前&…...

React Draggable插件实现拖拽功能
React Draggable插件实现拖拽功能1.下载Draggable插件2.引入Draggable插件3.设置一个div,并设置样式,并用Draggable包裹起来4.设置拖拽的范围5.Draggable常用props1.下载Draggable插件 npm install react-draggable2.引入Draggable插件 // 引入拖拽插件…...
MySQL-运算符
算术运算符: 加法运算-: 减法运算*: 乘法运算/: 除法运算,返回商%: 求余运算,返回余数例:创建n5表,插入数字100,查看数据表分别查看、-、*、/、%mysql> create table n5(-> num int); Query OK, 0 rows affected…...

Hudi-基本概念(时间轴、文件布局、索引、表类型、查询类型、数据写、数据读、Compaction)
文章目录基本概念时间轴(TimeLine)文件布局(File Layout)Hudi表的文件结构Hudi存储的两个部分Hudi的具体文件说明索引(Index)原理索引选项全局索引与非全局索引索引的选择策略对事实表的延迟更新对事件表的去重对维度表的随机更删…...
数据分享|中国各省、各市、各区县分年、分月、逐日平均气温数据(2000年~2019年)
今天分享给大家的是 2000 年~2019 年中国各省、各市、各县的分年、分月、逐日的平均气温数据(单位:摄氏度) 原始数据来源于国家气象科学数据共享服务平台-中国地面气候资料日值数据集(V3.0),原始数据是各个观测站点的日度数据,为了方便大家使用,我使用 Barnes 方法(…...

steam/csgo搬砖,2023年最暴利的项目
这个项目赚钱主要来源于两个地方: 1.比如说今天美元的汇率是1美元6.8人民币,那我们有特定的渠道能拿到1美元5.0-5.5左右人民币的价格,100美元的汇率差利润就有180元左右的利润,当然这个价格是根据国际的汇率上下会有浮动的。 2.…...

RDSDRDSPolarDBPolarDB-X的区别
RDS 阿里云关系型数据库(Relational Database Service,简称RDS),是一种稳定可靠、可弹性伸缩的在线数据库服务。 基于阿里云分布式文件系统和高性能存储,RDS支持MySQL、SQL Server、PostgreSQL和PPAS(Post…...

【Python学习笔记】30.Python3 命名空间和作用域
前言 本章介绍Python的命名空间和作用域。 命名空间 先看看官方文档的一段话: A namespace is a mapping from names to objects.Most namespaces are currently implemented as Python dictionaries。 命名空间(Namespace)是从名称到对象的映射,大…...

后量子 KEM 方案:Kyber
参考文献: Bos J, Ducas L, Kiltz E, et al. CRYSTALS-Kyber: a CCA-secure module-lattice-based KEM[C]//2018 IEEE European Symposium on Security and Privacy (EuroS&P). IEEE, 2018: 353-367.Avanzi R, Bos J, Ducas L, et al. Crystals-kyber[J]. NIST…...

2019年广东工业大学腾讯杯新生程序设计竞赛(同步赛)
同步赛链接 A-原初的信纸(最值,STL) 题意: 找 n 个数的最大值. 参考代码: void solve() {int n;std::cin >> n;std::vector<int> a(n);for (auto &c : a)std::cin >> c;std::cout << *max_element…...

生产Nginx现大量TIME-WAIT,连接耗尽,该如何处理?
背景说明: 在尼恩读者50交流群中,是不是有小伙伴问: 尼恩,生产环境 Nginx 后端服务大量 TIME-WAIT , 该怎么办? 除了Nginx进程之外,还有其他的后端服务如: 尼恩,生产环境…...

Linux服务器clang-13安装(环境变量配置)
1.从llvm的github网址选择合适的release合适的运行平台进行下载,下载官方预编译的二进制压缩包。 2.将下载好的压缩包进行本地上传。 使用scp命令进行上传 scp -r -P 端口号 本地文件路径 服务器ID等:服务器上目标地址 3.解压(tar命令) 4.环境变量配…...

【C++】C/C++内存管理模板初阶
文章目录一、 C/C内存管理1. C/C内存分布2. C内存管理方式3. operator new与operator delete函数4. new和delete的实现原理5. 定位new表达式6. 常见面试题malloc/free和new/delete的区别内存泄漏二、模板初阶1. 泛型编程2. 函数模板3. 类模板一、 C/C内存管理 1. C/C内存分布 …...
笙默考试管理系统-index展示
public class PageList<T> : List<T> { public int PageIndex { get; private set; } //页索引 public int PageSize { get; private set; }//页大小 public int TotalPage { get; private set; }//总页数 public int TotalCo…...

前端基础知识6
谈谈你对语义化标签的理解语义化标签就是具有语义的标签,它可以清晰地向我们展示它的作用和用途。 清晰的代码结构:在页面没有css的情况下,也能够呈现出清晰的代码内容 有利于SEO: 爬虫依赖标签来确定关键字的权重,因此可以和搜索…...
【项目精选】智慧物业管理系统
点击下载源码 1、 选题的背景、研究目的和意义 1)选题的背景 智慧物业是物业发展的必然趋势,是物业管理的一种新理念,是 新形势下社会管理创新的一种新模式。 随着人工智能、大数据、互联网等高新技术的发展,物业管理企 业先后试…...

解决HC-05/HC06等蓝牙模块的调试问题
解决HC-05/HC06等蓝牙模块的调试问题问题:1.无法使用USB转串口工具设置HC-05等蓝牙模块,具体问题是:发送AT指令,无回复;2.电脑如何连接HC-05模块,与模块通信(具体场景:HC-05模块的串…...

dfs(八)数字的全排列 (含有重复项与非重复项)
如果每个数字任意取的话。就不需要加book标志位 没有重复项数字的全排列_牛客题霸_牛客网 描述 给出一组数字,返回该组数字的所有排列 例如: [1,2,3]的所有排列如下 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1]. (以数字在数组中的位…...

基于微信小程序的医院挂号系统小程序
文末联系获取源码 开发语言:Java 框架:ssm JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7/8.0 数据库工具:Navicat11 开发软件:eclipse/myeclipse/idea Maven包:Maven3.3.9 浏览器…...

7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...

springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...

零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...

ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...

消息队列系统设计与实践全解析
文章目录 🚀 消息队列系统设计与实践全解析🔍 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡💡 权衡决策框架 1.3 运维复杂度评估🔧 运维成本降低策略 🏗️ 二、典型架构设计2.1 分布式事务最终一致…...
绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化
iOS 应用的发布流程一直是开发链路中最“苹果味”的环节:强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说,这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发(例如 Flutter、React Na…...
CppCon 2015 学习:REFLECTION TECHNIQUES IN C++
关于 Reflection(反射) 这个概念,总结一下: Reflection(反射)是什么? 反射是对类型的自我检查能力(Introspection) 可以查看类的成员变量、成员函数等信息。反射允许枚…...