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

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 星球的骑士&#xff0c;进入了一个奇怪的城堡。 城堡里边什么都没有&#xff0c;只有方形石头铺成的地面。 假设城堡地面是 n n n\times n nn 个方格。如图所示。 按习俗&#xff0c;骑士要从西北角走到东南角。 …...

oracle sql developer批量删除某个用户

随着navicate收费&#xff0c;还得破解&#xff0c;pl/sql developer配置麻烦&#xff0c;最近使用oracle sql developer来试试oracle的操作如何&#xff1b; 用着还行&#xff0c;没有卡顿现象&#xff0c; 最近要oracle sql developer批量删除某个用户下所有的表&#xff0…...

k8s 滚动更新控制(一)

在传统的应用升级时&#xff0c;通常采用的方式是先停止服务&#xff0c;然后升级部署&#xff0c;最后将新应用启动。这个过程面临一个问题&#xff0c;就是在某段时间内&#xff0c;服务是不可用的&#xff0c;对于用户来说是非常不友好的。而kubernetes滚动更新&#xff0c;…...

Java智慧工地APP源码带AI识别

智慧工地为建筑全生命周期赋能&#xff0c;用创新的可视化与智能化方法&#xff0c;降低成本&#xff0c;创造价值。 一、智慧工地APP概述 智慧工地”立足于互联网&#xff0c;采用云计算&#xff0c;大数据和物联网等技术手段&#xff0c;针对当前建筑行业的特点&#xff0c;…...

ME3116电源小板

最近设计一款PCB的时候使用微盟的dc dc电源ic踩了一个坑。 在使用me3116作为24v到5v的降压ic作为esp32系统前级的降压电路时&#xff0c;再没有铂电阻采样负载的情景下工作正常&#xff0c;带上负载后&#xff0c;ic工作不正常&#xff0c;过一段时间&#xff0c;后级电路会烧…...

摸准天气“小心思”,躲避恶劣天气“偷袭”

打开天气预报一看&#xff0c;天气真的很“善变”&#xff0c;既是高温又暴雨&#xff0c;偶尔还有台风路过&#xff0c;“蒸”的让人太太太难受了。看着天气在放晴和即将下雨之间“徘徊”&#xff0c;总是纠结带不带雨伞&#xff0c;让我的每次出门都成了一场冒险之旅。 持…...

Golang 局部变量、全局变量 声明

文章目录 一、局部变量二、全局变量 一、局部变量 四种声明方式 多变量声明&#xff1a; package mainimport "fmt"//局部变量声明 func main() {//方法一: 声明一个变量和数据类型&#xff0c;不初始化值&#xff1b;默认值为0&#xff1b;var lvA intfmt.Printl…...

软考高级之系统架构师之数据通信与计算机网络

概念 OSPF 在划分区域之后&#xff0c;OSPF网络中的非主干区域中的路由器对于到外部网络的路由&#xff0c;一定要通过ABR(区域边界路由器)来转发&#xff0c;既然如此&#xff0c;对于区域内的路由器来说&#xff0c;就没有必要知道通往外部网络的详细路由&#xff0c;只要由…...

牛客网华为OD前端岗位,面试题库练习记录01

题目一 质数因子 功能:输入一个正整数&#xff0c;按照从小到大的顺序输出它的所有质因子&#xff08;重复的也要列举&#xff09;&#xff08;如180的质因子为2 2 3 3 5 &#xff09; JavaScript Node ACM模式 const rl require("readline").createInterface({ i…...

Python web实战之Django 的缓存机制详解

关键词&#xff1a;Python、Web 开发、Django、缓存 1. 缓存是什么&#xff1f;为什么需要缓存&#xff1f; 在 Web 开发中&#xff0c;缓存是一种用于存储数据的临时存储区域。它可以提高应用程序的性能和响应速度&#xff0c;减轻服务器的负载。 当用户访问网页时&#xff…...

chatserver服务器开发笔记

chatserver服务器开发笔记 1 chatserver2 开发环境3 编译 1 chatserver 集群聊天服务器和客户端代码&#xff0c;基于muduo、redis、mysql实现。 学习于https://fixbug.ke.qq.com/ 本人已经挂github&#xff1a;https://github.com/ZixinChen-S/chatserver/tree/main 需要该项…...

DP——动态规划

DP——动态规划 动态规划算法动态规划的一般步骤特殊DP——背包0-1背包问题完全背包问题 总结 动态规划算法 当涉及到解决具有重叠子问题的优化问题时&#xff0c;动态规划是一种常用的算法技术。它通过将问题分解为一系列重叠子问题&#xff0c;并使用递归或迭代的方式来解决…...

【Windows 11】安装 Android子系统 和 Linux子系统

本文使用电脑系统&#xff1a; 文章目录 一、安卓子系统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 …...

秒杀库存解决方案

电商系统中秒杀是一种常见的业务场景需求&#xff0c;其中核心设计之一就是如何扣减库存。本篇主要分享一些常见库存扣减技术方案&#xff0c;库存扣减设计选择并非一味追求性能更佳&#xff0c;更多的应该考虑根据实际情况来进行架构取舍。在商品购买的过程中&#xff0c;库存…...

[免费在线] 将 PDF 转换为 Excel 或 Excel 转换为 PDF | 5 工具

有了免费的在线 PDF 转换器&#xff0c;您可以轻松免费在线将 PDF 转换为 Excel 或 Excel 转换为 PDF。这篇文章为您筛选了 5 个最常用的工具。要从存储介质恢复错误删除或丢失的 PDF 文档、Excel 电子表格、Word 文件或任何其他文件&#xff0c;您可以使用免费的数据恢复程序 …...

PLC求解弹簧质量模型微分方程数值解(RK4梯形图程序)

微分方程的数值求解,属于数学分析类课程涉及的内容。大家可以参看相关书籍对Runge-Kutta法的介绍,弹簧质量阻尼模型详细的微分方程介绍可以查看下面文章,链接如下: 弹簧质量阻尼系统前馈PID位置控制(PLC闭环仿真SCL+ST代码)_RXXW_Dor的博客-CSDN博客带前馈控制的博途PID程…...

CSDN编程题-每日一练(2023-08-14)

CSDN编程题-每日一练&#xff08;2023-08-14&#xff09; 一、题目名称&#xff1a;小股炒股二、题目名称&#xff1a;王子闯闸门三、题目名称&#xff1a;圆小艺 一、题目名称&#xff1a;小股炒股 时间限制&#xff1a;1000ms内存限制&#xff1a;256M 题目描述&#xff1a; …...

【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上

♥ 前 言 作为软件测试&#xff0c;大家都知道一些常用的网络协议是我们必须要了解和掌握的&#xff0c;比如 HTTP 协议&#xff0c;HTTPS 协议就是两个使用非常广泛的协议&#xff0c;所以也是面试官问的面试的时候问的比较多的两个协议&#xff1b;而且因为这两个协议有相…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...