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

按习俗,骑士要从西北角走到东南角。
可以横向或纵向移动,但不能斜着走,也不能跳跃。
每走到一个新方格,就要向正北方和正西方各射一箭。
(城堡的西墙和北墙内各有 n n n 个靶子)
同一个方格只允许经过一次。但不必做完所有的方格。
如果只给出靶子上箭的数目,你能推断出骑士的行走路线吗?
有时是可以的,比如如图中的例子。
本题的要求就是已知箭靶数字,求骑士的行走路径(测试数据保证路径唯一)
输入格式
第一行一个整数 N ( 0 < N < 20 ) N(0<N<20) N(0<N<20),表示地面有 N × N N \times N N×N 个方格。
第二行 N N N 个整数,空格分开,表示北边的箭靶上的数字(自西向东)
第三行 N N N 个整数,空格分开,表示西边的箭靶上的数字(自北向南)
输出格式
一行若干个整数,表示骑士路径。
为了方便表示,我们约定每个小格子用一个数字代表,从西北角开始编号 $:0,1,2,3 \cdots $。
比如,图中的方块编号为:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
样例 #1
样例输入 #1
4
2 4 3 4
4 3 3 3
样例输出 #1
0 4 5 1 2 3 7 11 10 9 13 14 15
提示
时限 1 秒, 256M。蓝桥杯 2016 年第七届国赛
众所周知,蓝桥杯奖水题不水
经过两个小时的折磨,终于做出来了,网上的题解能不能先把题目过了再发。。
使用dfs,运用减枝,开四个数组来标记,然后就是dfs常规的了,但是题目各种细节,使人心力交瘁
#include<bits/stdc++.h>
using namespace std;
const int N=25;
int g[N][N];
bool vis[N][N];
int path[450];
int n,cnt,k;
bool f;
int ax[N],ay[N];
int bx[N],by[N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
bool check()
{for(int i=1;i<=n;i++){if(bx[i]!=ax[i]||by[i]!=ay[i])return 0;}return 1;
}void dfs(int x,int y)
{if(f) return ;if(x==n&&y==n&&check()){for(int i=0;i<cnt;i++)cout<<path[i]<<" ";f=1;return;}for(int i=0;i<4;i++){int xxx=x+dx[i],yyy=y+dy[i];if(vis[xxx][yyy]||xxx<1||xxx>n||yyy<1||yyy>n||bx[xxx]>=ax[xxx]||by[yyy]>=ay[yyy])continue;bx[xxx] ++;by[yyy] ++;vis[xxx][yyy]=true;path[cnt++]=g[xxx][yyy];dfs(xxx,yyy);bx[xxx] --;by[yyy] --;vis[xxx][yyy]=false;path[cnt--]=-1; }}
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>ay[i];for(int i=1;i<=n;i++)cin>>ax[i];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){g[i][j]=k++;}}vis[1][1]=true;path[0]=0;cout<<"0"<<" ";bx[1]=1,by[1]=1;dfs(1,1);return 0;
}
相关文章:
P8642 [蓝桥杯 2016 国 AC] 路径之谜
[蓝桥杯 2016 国 AC] 路径之谜 题目描述 小明冒充 X X X 星球的骑士,进入了一个奇怪的城堡。 城堡里边什么都没有,只有方形石头铺成的地面。 假设城堡地面是 n n n\times n nn 个方格。如图所示。 按习俗,骑士要从西北角走到东南角。 …...
oracle sql developer批量删除某个用户
随着navicate收费,还得破解,pl/sql developer配置麻烦,最近使用oracle sql developer来试试oracle的操作如何; 用着还行,没有卡顿现象, 最近要oracle sql developer批量删除某个用户下所有的表࿰…...
k8s 滚动更新控制(一)
在传统的应用升级时,通常采用的方式是先停止服务,然后升级部署,最后将新应用启动。这个过程面临一个问题,就是在某段时间内,服务是不可用的,对于用户来说是非常不友好的。而kubernetes滚动更新,…...
Java智慧工地APP源码带AI识别
智慧工地为建筑全生命周期赋能,用创新的可视化与智能化方法,降低成本,创造价值。 一、智慧工地APP概述 智慧工地”立足于互联网,采用云计算,大数据和物联网等技术手段,针对当前建筑行业的特点,…...
ME3116电源小板
最近设计一款PCB的时候使用微盟的dc dc电源ic踩了一个坑。 在使用me3116作为24v到5v的降压ic作为esp32系统前级的降压电路时,再没有铂电阻采样负载的情景下工作正常,带上负载后,ic工作不正常,过一段时间,后级电路会烧…...
摸准天气“小心思”,躲避恶劣天气“偷袭”
打开天气预报一看,天气真的很“善变”,既是高温又暴雨,偶尔还有台风路过,“蒸”的让人太太太难受了。看着天气在放晴和即将下雨之间“徘徊”,总是纠结带不带雨伞,让我的每次出门都成了一场冒险之旅。 持…...
Golang 局部变量、全局变量 声明
文章目录 一、局部变量二、全局变量 一、局部变量 四种声明方式 多变量声明: package mainimport "fmt"//局部变量声明 func main() {//方法一: 声明一个变量和数据类型,不初始化值;默认值为0;var lvA intfmt.Printl…...
软考高级之系统架构师之数据通信与计算机网络
概念 OSPF 在划分区域之后,OSPF网络中的非主干区域中的路由器对于到外部网络的路由,一定要通过ABR(区域边界路由器)来转发,既然如此,对于区域内的路由器来说,就没有必要知道通往外部网络的详细路由,只要由…...
牛客网华为OD前端岗位,面试题库练习记录01
题目一 质数因子 功能:输入一个正整数,按照从小到大的顺序输出它的所有质因子(重复的也要列举)(如180的质因子为2 2 3 3 5 ) JavaScript Node ACM模式 const rl require("readline").createInterface({ i…...
Python web实战之Django 的缓存机制详解
关键词:Python、Web 开发、Django、缓存 1. 缓存是什么?为什么需要缓存? 在 Web 开发中,缓存是一种用于存储数据的临时存储区域。它可以提高应用程序的性能和响应速度,减轻服务器的负载。 当用户访问网页时ÿ…...
chatserver服务器开发笔记
chatserver服务器开发笔记 1 chatserver2 开发环境3 编译 1 chatserver 集群聊天服务器和客户端代码,基于muduo、redis、mysql实现。 学习于https://fixbug.ke.qq.com/ 本人已经挂github:https://github.com/ZixinChen-S/chatserver/tree/main 需要该项…...
DP——动态规划
DP——动态规划 动态规划算法动态规划的一般步骤特殊DP——背包0-1背包问题完全背包问题 总结 动态规划算法 当涉及到解决具有重叠子问题的优化问题时,动态规划是一种常用的算法技术。它通过将问题分解为一系列重叠子问题,并使用递归或迭代的方式来解决…...
【Windows 11】安装 Android子系统 和 Linux子系统
本文使用电脑系统: 文章目录 一、安卓子系统1.1 安装 WSA1.2 使用 二、Linux子系统2.1 安装 WSL 以及WSL 相关概念2.2 安装一个Linux发行版2.21 从Microsoft Store 安装2.22 用命令安装 2.23 拓展 三、拓展3.1 存储位置3.2 虚拟化技术3.3 Windows 虚拟内存3.3 wsl …...
秒杀库存解决方案
电商系统中秒杀是一种常见的业务场景需求,其中核心设计之一就是如何扣减库存。本篇主要分享一些常见库存扣减技术方案,库存扣减设计选择并非一味追求性能更佳,更多的应该考虑根据实际情况来进行架构取舍。在商品购买的过程中,库存…...
[免费在线] 将 PDF 转换为 Excel 或 Excel 转换为 PDF | 5 工具
有了免费的在线 PDF 转换器,您可以轻松免费在线将 PDF 转换为 Excel 或 Excel 转换为 PDF。这篇文章为您筛选了 5 个最常用的工具。要从存储介质恢复错误删除或丢失的 PDF 文档、Excel 电子表格、Word 文件或任何其他文件,您可以使用免费的数据恢复程序 …...
PLC求解弹簧质量模型微分方程数值解(RK4梯形图程序)
微分方程的数值求解,属于数学分析类课程涉及的内容。大家可以参看相关书籍对Runge-Kutta法的介绍,弹簧质量阻尼模型详细的微分方程介绍可以查看下面文章,链接如下: 弹簧质量阻尼系统前馈PID位置控制(PLC闭环仿真SCL+ST代码)_RXXW_Dor的博客-CSDN博客带前馈控制的博途PID程…...
CSDN编程题-每日一练(2023-08-14)
CSDN编程题-每日一练(2023-08-14) 一、题目名称:小股炒股二、题目名称:王子闯闸门三、题目名称:圆小艺 一、题目名称:小股炒股 时间限制:1000ms内存限制:256M 题目描述: …...
【SA8295P 源码分析】69 - Android 侧添加支持 busybox telnetd 服务
【SA8295P 源码分析】69 - Android 侧添加支持 busybox telnetd 服务 一、下载 busybox-1.36.1.tar.bz2 源码包二、编译 busybox 源码三、将编译后的 busybox 打包编入Android 镜像中系列文章汇总见:《【SA8295P 源码分析】00 - 系列文章链接汇总》 本文链接:《【SA8295P 源码…...
OpenCV图像处理——模版匹配和霍夫变换
目录 模版匹配原理实现 霍夫变换霍夫线检测 模版匹配 原理 实现 rescv.matchTemplate(img,template,method)import numpy as np import cv2 as cv import matplotlib.pyplot as pltimgcv.imread(./汪学长的随堂资料/6/模板匹配/lena.jpg) templatecv.imread(./汪学长的随堂资…...
面试官的几句话,差点让我挂在HTTPS上
♥ 前 言 作为软件测试,大家都知道一些常用的网络协议是我们必须要了解和掌握的,比如 HTTP 协议,HTTPS 协议就是两个使用非常广泛的协议,所以也是面试官问的面试的时候问的比较多的两个协议;而且因为这两个协议有相…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
ubuntu22.04 安装docker 和docker-compose
首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...
