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 浏览器…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)
目录 🔍 若用递归计算每一项,会发生什么? Horners Rule(霍纳法则) 第一步:我们从最原始的泰勒公式出发 第二步:从形式上重新观察展开式 🌟 第三步:引出霍纳法则&…...

Python环境安装与虚拟环境配置详解
本文档旨在为Python开发者提供一站式的环境安装与虚拟环境配置指南,适用于Windows、macOS和Linux系统。无论你是初学者还是有经验的开发者,都能在此找到适合自己的环境搭建方法和常见问题的解决方案。 快速开始 一分钟快速安装与虚拟环境配置 # macOS/…...

CVE-2023-25194源码分析与漏洞复现(Kafka JNDI注入)
漏洞概述 漏洞名称:Apache Kafka Connect JNDI注入导致的远程代码执行漏洞 CVE编号:CVE-2023-25194 CVSS评分:8.8 影响版本:Apache Kafka 2.3.0 - 3.3.2 修复版本:≥ 3.4.0 漏洞类型:反序列化导致的远程代…...