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 协议就是两个使用非常广泛的协议,所以也是面试官问的面试的时候问的比较多的两个协议;而且因为这两个协议有相…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
RushDB开源程序 是现代应用程序和 AI 的即时数据库。建立在 Neo4j 之上
一、软件介绍 文末提供程序和源码下载 RushDB 改变了您处理图形数据的方式 — 不需要 Schema,不需要复杂的查询,只需推送数据即可。 二、Key Features ✨ 主要特点 Instant Setup: Be productive in seconds, not days 即时设置 :在几秒钟…...
基于小程序老人监护管理系统源码数据库文档
摘 要 近年来,随着我国人口老龄化问题日益严重,独居和居住养老机构的的老年人数量越来越多。而随着老年人数量的逐步增长,随之而来的是日益突出的老年人问题,尤其是老年人的健康问题,尤其是老年人产生健康问题后&…...
以太网PHY布局布线指南
1. 简介 对于以太网布局布线遵循以下准则很重要,因为这将有助于减少信号发射,最大程度地减少噪声,确保器件作用,最大程度地减少泄漏并提高信号质量。 2. PHY设计准则 2.1 DRC错误检查 首先检查DRC规则是否设置正确,然…...
