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

蓝桥杯—数字接龙(dfs+减枝)

一.题目

二.思路

一看就是迷宫问题的变种,从左上角到达右下角,要解决

1.8个方向的方向向量,用dx,dy数组代表方向向量

2.要按照一个规律的数值串进行搜索0,1,2,k-1,0,1,2......,这个好实现只需要在dfs方法中加入一个下一个数值的参数搜索就行

3.核心减枝:斜对角线不能交叉(本题难点),这里用了一个四维数组来标记走过的对角线

(x,y)->(xx,yy)代表从对角线连线,mark[x][y][xx][yy],mark数组只用于记录对角线连线

由下图可知:

在判断是否能进行对角线连线时只需要检测mark[x][b][a][y]即可

三.代码

public static int n;public static int[] dx = {-1,-1,0,1,1,1,0,-1};//八个方向的方向向量,注意要按照题目要求public static int[] dy = {0,1,1,1,0,-1,-1,-1};public static boolean[][] mark = new boolean[11][11];//判断数组public static boolean[][][][] mark1 = new boolean[12][12][12][12];//判断是否交叉public static int[] res = new int[100];//记录答案public static boolean t;//用于记录是否有路径可以到达右下角public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt();int k = scan.nextInt()-1;int[][] map = new int[n+1][n+1];for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){map[i][j] = scan.nextInt();}}mark[1][1] = true;dfs(1,1,map,k,0,1);//数据范围很小dfs暴力搜索if(t==false) System.out.println(-1);scan.close();}public static void dfs(int x,int y,int[][] map,int k,int index,int cnt)//index走了几个格子,cnt下一步数值{if(t==true) return;if(index == n*n-1&&x==n&&y==n)//说明走完了,因为是按照字典顺序进行搜索的,所以第一个结果就是字典顺序最小的结果{t = true;for(int i = 0;i<n*n-1;i++){System.out.print(res[i]);}System.out.println();return;}for(int i = 0;i<8;i++){int xx = x + dx[i];int yy = y + dy[i];if(check(xx,yy,cnt,map))//说明没有走过,并且数值满足{if(i==1||i==3||i==5||i==7)//斜线走的(x,y)->(xx,yy){if(mark1[x][yy][xx][y]==true)continue;mark1[x][y][xx][yy] = true;mark1[xx][yy][x][y] = true;}mark[xx][yy] = true;res[index] = i;//记录结果int tmp = cnt;if(cnt==k)  cnt = 0;else cnt++;dfs(xx,yy,map,k,index+1,cnt);mark[xx][yy] = false;cnt = tmp;if(i==1||i==3||i==5||i==7) {//注意只有在i为奇数时才会操作对角线,这里的作用也是减枝mark1[x][y][xx][yy] = false;mark1[xx][yy][x][y] =false;}}}}public static boolean check(int x,int y,int cnt,int[][] map)//减枝{if(x>=1&&x<=n&&y>=1&&y<=n&&mark[x][y]==false)//根据题意出现交叉的无所谓不用处理{if(map[x][y]==cnt) return true;}return false;}

相关文章:

蓝桥杯—数字接龙(dfs+减枝)

一.题目 二.思路 一看就是迷宫问题的变种&#xff0c;从左上角到达右下角&#xff0c;要解决 1.8个方向的方向向量&#xff0c;用dx&#xff0c;dy数组代表方向向量 2.要按照一个规律的数值串进行搜索0&#xff0c;1&#xff0c;2&#xff0c;k-1&#xff0c;0&#xff0c;1…...

Solidity智能合约漏洞类型与解题思路指南

一、常见漏洞类型与通俗解释 1. 重入攻击(Reentrancy) 🌀 通俗解释:就像你去银行取钱,柜台人员先给你钱,然后再记账。你拿到钱后立即又要求取钱,由于账还没记,柜台又给你一次钱,这样循环下去你就能拿走银行所有的钱。 漏洞原理:合约在更新状态前调用外部合约,允许…...

临床 不等于 医学-《分析模式》漫谈52

DDD领域驱动设计批评文集 做强化自测题获得“软件方法建模师”称号 《软件方法》各章合集 “Analysis Patterns”的第4章“企业财务观察”有这么一句话&#xff1a; An important point about this model——a reflection of its clinical background 2004&#xff08;机械…...

鸿蒙应用开发中的 Stack 布局模式

在鸿蒙(HarmonyOS)应用开发中&#xff0c;Stack 布局模式是一种非常灵活的布局方式&#xff0c;类似于其他开发框架中的 StackPanel 或 AbsoluteLayout。它允许子组件按照层级关系进行堆叠&#xff0c;后添加的组件会覆盖在先添加的组件之上。开发者可以通过设置组件的位置、大…...

仿modou库one thread one loop式并发服务器

源码&#xff1a;田某super/moduo 目录 SERVER模块&#xff1a; Buffer模块&#xff1a; Socket模块&#xff1a; Channel模块&#xff1a; Connection模块&#xff1a; Acceptor模块&#xff1a; TimerQueue模块&#xff1a; Poller模块&#xff1a; EventLoop模块&a…...

【AI学习】初步了解Gradio

Gradio 是一个开源的 Python 库&#xff0c;专注于快速构建交互式 Web 界面&#xff0c;特别适用于机器学习模型、数据科学项目或任意 Python 函数的演示与部署。它通过极简的代码实现前后端一体化&#xff0c;无需前端开发经验即可创建功能丰富的应用。以下是 Gradio 的核心特…...

C++11QT复习 (十四)

文章目录 Day9 数据结构学习笔记&#xff08;2025.04.01&#xff09;一、C基础快速回顾二、STL&#xff08;标准模板库&#xff09;三、常见容器及其对应的数据结构四、容器操作演示1. 基本容器使用2. 异构类型容器 五、迭代器详解特点示例用户自定义结构体访问成员 六、算法库…...

ThreadCache

目录 一、Freelist 二、ThreadCache 三、哈希桶映射规则 一、Freelist 在之前整体框架介绍的时候&#xff0c;我们曾说过ThreadCache是一个哈希桶的结构。每一个桶都要存同一个大小的对象块&#xff08;即最小块的内存&#xff09;。 那么我们使用FreeList来…...

c++中同步和异步,阻塞和非阻塞原理以及机制

在C中&#xff0c;同步与异步、阻塞与非阻塞是并发编程中的重要概念&#xff0c;它们描述了程序在执行任务时的行为模式。理解这些概念对于设计高效、响应良好的并发程序至关重要。下面我将详细介绍这些概念的原理和机制。 1. 同步与异步 同步&#xff08;Synchronous&#x…...

Python项目打包指南:PyInstaller与SeleniumWire的兼容性挑战及解决方案

前言 前段时间做一个内网开发的需求&#xff0c;要求将selenium程序打包成.exe放在内网的win7上运行&#xff0c;在掘金搜了一圈也没有发现相关文章&#xff0c;因此将过程中踩到的坑记录分享一下。 本文涵盖了具体打包操作、不同模块和依赖项的兼容性解决方案&#xff0c;以…...

浅谈微信视频号推荐算法

这次可能会稍微有点干货&#xff0c;但保证不晦涩~ 一、算法推荐的本质&#xff1a;猜你喜欢 vs 社交绑架​ 视频号的推荐系统本质上在做两件事&#xff1a; ​预测你的兴趣​&#xff1a;通过你的浏览、点赞、评论、分享等行为&#xff0c;分析你的偏好。​满足社交需求​&…...

selenium 常用方法

selenium 库的常用方法&#xff1a; 方法说明示例代码webdriver.Chrome()初始化 Chrome 浏览器实例。driver webdriver.Chrome()driver.get(url)访问指定的 URL 地址。driver.get("https://example.com")driver.find_element(By, value)查找第一个匹配的元素。elem…...

springboot中使用async实现异步编程

目录 1.说明 2.实现原理 3.示例 4.总结 1.说明 Async 是 Spring 框架提供的一个注解&#xff0c;用于标记方法为异步执行。被标记的方法将在调用时立即返回&#xff0c;而实际的方法执行将在单独的线程中进行。 Async 注解有一个可选属性&#xff1a;指定要使用的特定线程…...

【2024年蓝桥杯Java B组】省赛真题详细解析

【2024年蓝桥杯Java B组】省赛真题 距离比赛仅剩5天&#xff0c;大多数省份可能完成3-4题即可拿到省奖&#xff0c;2025年想要拿到省奖&#xff0c;需要高效利用时间&#xff0c;重点突破关键知识点和题型。这里以【2024年蓝桥杯Java B组省赛真题】为例&#xff0c;梳理我们最后…...

SQL:DDL(数据定义语言)和DML(数据操作语言)

目录 什么是SQL&#xff1f; 1. DDL&#xff08;Data Definition Language&#xff0c;数据定义语言&#xff09; 2. DML&#xff08;Data Manipulation Language&#xff0c;数据操作语言&#xff09; DDL和DML的区别 什么是SQL&#xff1f; SQL&#xff08;Structured …...

机器学习核心概念、算法分类与应用场景全解析

文章目录 一、基础任务与算法分类1. 分类任务&#xff08;监督学习&#xff09;2. 回归任务&#xff08;监督学习&#xff09;3. 聚类任务&#xff08;无监督学习&#xff09; 二、关键流程与技术细节1. 数据预处理2. 特征工程3. 数据集划分与评估 三、进阶技术1.深度学习2.强化…...

【leetcode】—416.分割等和子集

✏️ 关于专栏&#xff1a;专栏用于记录 LeetCode 中做题与总结 文章目录 分割等和子集▐ 题目描述▐ 题目示例▐ 题目提示▐ 思路&代码方法&#xff1a;动态规划 分割等和子集 ▐ 题目描述 题目链接&#xff1a;分割等和子集 给你一个 只包含正整数 的 非空 数组 nums …...

jemeter 之mysql驱动问题

问题 java.sql.SQLException: No suitable driver found for jdbc:mysql 解决 先把jar放到lib下 检查 JMeter 的 Classpath 在 JMeter 中&#xff0c;JDBC 驱动需要手动添加到 Classpath 中。 打开 JMeter 安装目录下的 bin/jmeter.properties 文件&#xff0c;找到 user.cla…...

隐私计算的崛起:数据安全的未来守护者

在信息技术&#xff08;IT&#xff09;的滚滚浪潮中&#xff0c;一种新兴技术正以惊人速度崭露头角——隐私计算&#xff08;Privacy-Preserving Computation&#xff09;。2025 年&#xff0c;随着数据泄露事件频发、全球隐私法规日益严格&#xff0c;以及企业对数据协作需求的…...

Excel计数、求和、统计、计算类函数

目录 一、计数函数1. COUNT2. COUNTA3. COUNTBLANK4. COUNTIF5. COUNTIFS 二、求和函数1. SUM2. SUMIF3. SUMIFS4. SUMPRODUCT 三、统计函数1. AVERAGE2. AVERAGEA3. AVERAGEIF 函数4. AVERAGEIFS 函数 四、其他常用计算函数1. MAX 与 MIN2. RANK3. MOD4. ROUND5. FLOOR6. INT7…...

解决 Kubernetes 中容器 `CrashLoopBackOff` 问题的实战经验

在 Kubernetes 集群中&#xff0c;容器状态为 CrashLoopBackOff 通常意味着容器启动失败&#xff0c;并且 Kubernetes 正在不断尝试重启它。这种状态表明容器内可能存在严重错误&#xff0c;如应用异常、依赖服务不可用、配置错误等。本文将分享一次实际排障过程&#xff0c;并…...

北师大具身AI的虚拟世界扩展!UNREALZOO:为具身智能打造高逼真度的虚拟世界

作者&#xff1a;Fangwei Zhong, Kui Wu, Churan Wang, Hao Chen, Hai Ci, Zhoujun Li, Yizhou Wang 单位&#xff1a;北京师范大学&#xff0c;北京航空航天大学&#xff0c;北京大学&#xff0c;BIGAI&#xff0c;澳门城市大学&#xff0c;新加坡国立大学 论文标题&#xf…...

2025 年浙江保安员职业资格考试高效备考指南​

浙江以创新活力著称&#xff0c;保安行业也在不断革新。2025 年考试报考条件常规&#xff0c;报名主要通过浙江省保安服务监管信息系统&#xff0c;方便快捷。​ 理论考试在传统知识基础上&#xff0c;加大对智能安防技术应用的考查&#xff0c;如人脸识别系统、智能监控报警系…...

创意设计:动态彩色数学爱心

设计理念 数学之美&#xff1a;使用心形线的数学方程&#xff08;心形曲线&#xff09;生成爱心形状。视觉吸引力&#xff1a;通过 Python 的 colorama 库添加颜色渐变效果。动态感&#xff1a;加入简单的动画&#xff0c;让爱心“跳动”。技术魅力&#xff1a;结合模块化编程…...

C++动态内存管理完全指南:从基础到现代最佳实践

一、动态内存基础原理 1.1 内存分配层次结构 内存类型生命周期分配方式典型使用场景静态存储区程序整个运行期编译器分配全局变量、静态变量栈内存函数作用域自动分配/释放局部变量堆内存手动控制new/malloc分配动态数据结构 1.2 基本内存操作函数 // C风格 void* malloc(s…...

ebpf: CO-RE, BTF, and Libbpf(一)

本文内容主要来源于Learning eBPF&#xff0c;可阅读原文了解更全面的内容。 概述 一个ebpf程序可以在一个kernel版本中编译&#xff0c;而在另外一个kernel版本上运行&#xff0c;即便两个kernel版本中有些结构体有变化。而BTF(BPF Type Format) 是能让ebpf有这种强大兼容性…...

Linux 递归查找并删除目录下的文件

在 Linux 中&#xff0c;可以使用 find 命令递归查找并删除目录下的文件 1、示例命令 find /path/to/directory -type f -name "filename_pattern" -exec rm -f {} 2、参数说明 /path/to/directory&#xff1a;要查找的目标目录type f&#xff1a;表示查找文件&am…...

使用人工智能大模型腾讯元宝,如何快速编写活动记录?

今天我们学习使用人工智能大模型腾讯元宝&#xff0c;如何快速编写活动记录&#xff1f; 手把手学习视频地址https://edu.csdn.net/learn/40402/666457 第一步在腾讯元宝对话框中输入如何协助老师写教研活动记录&#xff0c;通过提问&#xff0c;我们了解了老师写教研活动记录…...

File 类的用法和 InputStream, OutputStream 的用法

1 文件系统的操作 创建文件&#xff0c;删除文件&#xff0c;创建目录&#xff0c;重命名文件&#xff0c;判定文件存在... Java中提供file类进行文件系统操作&#xff0c;使用路径进行初始化表示具体的文件&#xff08;可以存在&#xff0c;也可以不存在&#xff09;&#xf…...

buuctf--[湖南省赛2019]Findme

目录 前沿 解题过程 分析 ​p1 P2 p3 p4 p5 前沿 其实对于这道题呢&#xff0c;我的想法是不知道怎么判断的&#xff0c;这个题你说他难吧&#xff0c;他用的都是比较基础的东西&#xff0c;说他简单吧&#xff0c;他有太复杂的过程&#xff0c;总体来讲&#xff0…...

【从0到1学MybatisPlus】MybatisPlus入门

Mybatis-Plus 使用场景 大家在日常开发中应该能发现&#xff0c;单表的CRUD功能代码重复度很高&#xff0c;也没有什么难度。而这部分代码量往往比较大&#xff0c;开发起来比较费时。 因此&#xff0c;目前企业中都会使用一些组件来简化或省略单表的CRUD开发工作。目前在国…...

【S32M244 RTD200P04 LLD篇8】S32M244 PWM ADC LLD demo

【S32M244 RTD200P04 LLD篇8】S32M244 PWM ADC LLD demo 一&#xff0c;文档简介二&#xff0c;PWMTRGMUXPDBADC 2ch 软件配置与实现2.1 软硬件版本平台2.2 Demo CT 模块配置2.2.1 引脚配置2.2.2 时钟配置2.2.3 外设配置 2.3主程序调用情况 三&#xff0c; 测试结果 一&#xf…...

(蓝桥杯)动态规划蓝桥杯竞赛指南:动态规划解决最少钞票数问题(超详细解析+代码实现)

问题描述 近期&#xff0c;黄开的银行新发行了一种面额为 4 的钞票&#xff0c;使得钞票种类增至 5 种&#xff1a;20、10、5、4 和 1 元。银行在发钞时十分“节俭”&#xff0c;当有客户取钱时&#xff0c;需要以最少的钞票数来满足取款金额。 问题要求&#xff1a; 对于给定…...

深度:善用人工智能推动高等教育学习、教学与治理的深层变革

在人工智能技术与教育深度融合的当下,高等教育正经历着前所未有的范式转型。从学习方式的革新到教学模式的重构,再到治理体系的升级,人工智能已不再仅仅是辅助工具,而是成为重塑高等教育生态的核心驱动力。这一变革浪潮中,生成式人工智能(Generative AI)作为技术前沿的代…...

python全栈-JavaScript

python全栈-js 文章目录 js基础变量与常量JavaScript引入到HTML文件中JavaScript注释与常见输出方式 数据类型typeof 显示数据类型算数运算符之加法运算符运算符之算术运算符运算符之赋值运算符运算符之比较运算符运算符之布尔运算符运算符之位运算符运算符优先级类型转换 控制…...

Django信号使用完全指南示例

推荐超级课程: 本地离线DeepSeek AI方案部署实战教程【完全版】Docker快速入门到精通Kubernetes入门到大师通关课AWS云服务快速入门实战目录 **引言:****先决条件:****目录:****1. 什么是Django信号?****2:设置你的Django项目****2.1. 安装Django**2.2. 创建一个Django项…...

# 深入理解GPT:架构、原理与应用示例

深入理解GPT&#xff1a;架构、原理与应用示例 一、引言 GPT&#xff08;Generative Pre-trained Transformer&#xff09;系列模型自2018年问世以来&#xff0c;凭借其强大的文本生成能力和多任务适应性&#xff0c;彻底改变了自然语言处理&#xff08;NLP&#xff09;领域。…...

C语言递归

一、递归的核心原理 1. 递归的本质 自相似性&#xff1a;将问题分解为与原问题结构相同但规模更小的子问题&#xff08;如树的遍历、分治算法&#xff09;。 栈机制&#xff1a;每次递归调用都会在内存栈中创建一个新的函数栈帧&#xff0c;保存当前状态&#xff08;参数、局…...

Jetpack Compose 基础组件学习2.0

文章目录 1、kotlin版本修改问题修改2、前言&#xff1a;参考知识点&#xff1a; 3、文字超链接的实现新版实现&#xff08;Text AnnotatedString实现效果&#xff09; 4、文字强调效果&#xff08; Material3 的透明度方案&#xff09;material依赖实现文字强调效果&#xff…...

MySQL SQL 优化的10个关键方向

1. 索引优化 合理创建索引&#xff1a;为高频查询条件、JOIN字段、排序字段创建索引 复合索引设计&#xff1a;遵循最左前缀原则&#xff0c;将选择性高的列放在前面 避免索引失效&#xff1a;防止索引列上使用函数、类型转换、OR条件不当使用 覆盖索引&#xff1a;尽量让查…...

babel-runtime 如何缩小打包体积

&#x1f916; 作者简介&#xff1a;水煮白菜王&#xff0c;一位前端劝退师 &#x1f47b; &#x1f440; 文章专栏&#xff1a; 前端专栏 &#xff0c;记录一下平时在博客写作中&#xff0c;总结出的一些开发技巧和知识归纳总结✍。 感谢支持&#x1f495;&#x1f495;&#…...

VMware Fusion虚拟机Mac版安装CentOS Stream 9

VMware Fusion虚拟机Mac版安装CentOS Stream 9 文章目录 VMware Fusion虚拟机Mac版安装CentOS Stream 9一、介绍二、效果三、下载 一、介绍 CentOS Stream 9是CentOS Stream发行版的最新主要版本&#xff0c;旨在提供Red Hat Enterprise Linux&#xff08;RHEL&#xff09;的每…...

手搓多模态-05 transformer编码层

前情回顾 前面我们已经实现一个图像嵌入层和顶层的模型调度&#xff1a; class SiglipVisionTransformer(nn.Module): ##视觉模型的第二层&#xff0c;将模型的调用分为了图像嵌入模型和transformer编码器模型的调用def __init__(self, config:SiglipVisionConfig):super().__i…...

LightTrack + VOT2019 + Jetson 部署全流程指南【轻量级目标跟踪】

LightTrack VOT2019 Jetson 部署全流程指南【轻量级目标跟踪】 &#x1f527; 1. 环境准备&#xff08;Jetson 平台&#xff09;推荐配置&#xff1a;⚙️ 安装 Python 3.6 虚拟环境&#xff08;Jetson 原生 Python 版本较新&#xff09; &#x1f4e5; 2. 下载 LightTrack 源…...

【Easylive】视频删除方法详解:重点分析异步线程池使用

【Easylive】项目常见问题解答&#xff08;自用&持续更新中…&#xff09; 汇总版 方法整体功能 这个deleteVideo方法是一个综合性的视频删除操作&#xff0c;主要完成以下功能&#xff1a; 权限验证&#xff1a;检查视频是否存在及用户是否有权限删除核心数据删除&…...

(C语言)循环单链表(数据结构)(指针)(循环列表教程)

目录 源代码&#xff1a; 代码详解&#xff1a; 1. 头文件和宏定义 2. 类型定义 3. 初始化链表 4. 判断链表是否为空 5. 求链表的长度 6. 清空链表 7. 销毁链表 8. 链表的插入&#xff08;头插法&#xff09; 9. 链表的插入&#xff08;尾插法&#xff09; 10. 查看…...

Debian 12 服务器搭建Beego环境

一、Debian 12系统准备 1.更新系统 #apt update && apt upgrade -y 2.安装基础工具 #apt install -y git curl wget make gcc 二、安装Go环境 Go语言的镜像官网&#xff1a;https://golang.google.cn/ 1.下载go最新版 #cd /usr/local/src #wget -o https://golang.go…...

淘宝商品评论API接口概述及JSON数据参考(测试)

前言 一、淘宝商品评论API接口概述 淘宝商品评论API接口是淘宝开放平台提供的一项服务&#xff0c;允许开发者通过HTTP请求获取指定商品的评论数据。这些数据包括评论内容、评论者信息、评分、评论时间等&#xff0c;为开发者提供了丰富的商品评价信息&#xff0c;有助于分析…...

AI:决策树、决策森林与随机森林

决策树与随机森林:从原理到实战的全面解析(2025最新版) 引言 在机器学习的世界里,决策树和森林模型(包括随机森林)常常是数据科学家们常用的工具之一。无论是初学者还是资深从业者,理解这些模型的原理和应用,都能帮助你在数据分析和预测任务中获得更好的结果。本文将…...

图形化编程语言:低代码赛道的技术革命与范式突破

在 2024 年 Gartner 低代码平台魔力象限报告中&#xff0c;传统低代码厂商市场份额增速放缓至 12%&#xff0c;而图形化编程语言赛道融资额同比激增 370%。本文深度剖析低代码平台的技术瓶颈&#xff0c;系统阐释图形化编程语言的核心优势&#xff0c;揭示其如何重构软件开发范…...