【蓝桥杯集训·每日一题】AcWing 3502. 不同路径数
文章目录
- 一、题目
- 1、原题链接
- 2、题目描述
- 二、解题报告
- 1、思路分析
- 2、时间复杂度
- 3、代码详解
- 三、知识风暴
一、题目
1、原题链接
3502. 不同路径数
2、题目描述
给定一个 n×m 的二维矩阵,其中的每个元素都是一个 [1,9] 之间的正整数。
从矩阵中的任意位置出发,每次可以沿上下左右四个方向前进一步,走过的位置可以重复走。
走了 k 次后,经过的元素会构成一个 (k+1) 位数。
请求出 一共可以走出多少个不同的 (k+1) 位数。
输入格式
第一行包含三个整数 n,m,k。
接下来 n 行,每行包含 m 个空格隔开的整数,表示给定矩阵。
输出格式
输出一个整数,表示可以走出的不同 (k+1) 位数的个数。
数据范围
对于 30% 的数据, 1≤n,m≤2,0≤k≤2
对于 100% 的数据,1≤n,m≤5,0≤k≤5,m×n>1
输入样例:
3 3 2 1 1 1 1 1 1 2 1 1
输出样例:
5
样例解释
一共有 5 种可能的 3 位数:
111 112 121 211 212
二、解题报告
1、思路分析
思路来源:y总讲解视频
y总yyds
(1)因为走过的位置可以重复走,所以针对每个点,它四个方向且在范围中的点都可以走。
(2)利用dfs对每个点可能构成的(k+1)位数进行搜索,然后将构成的数加入哈希表中去重,最终哈希表中元素的数量,即为不同的(k+1)位数的个数。
(3)模拟上述过程,输出答案,即为所求。
2、时间复杂度
时间复杂度为O(n* m *4k)
3、代码详解
#include <iostream>
#include <unordered_set>
using namespace std;
const int N=10;
int g[N][N];
int dx[]={-1,1,0,0},dy[]={0,0,-1,1}; //记录上下左右四个方向的坐标偏移量
int n,m,k;
unordered_set<int> se; //记录不同数字的个数
void dfs(int x,int y,int u,int sum){ //(x,y)为坐标,u代表当前是第几位数(0~k),sum代表当前数字组成的数的值if(u==k){ //如果已经有k个数字,结束,收获答案加入哈希表中,并回溯se.insert(sum);return;}for(int i=0;i<4;i++){ //否则,每个点都可以向上下左右四个方向走,依次枚举int a=x+dx[i],b=y+dy[i];if(a>=0&&a<n&&b>=0&&b<m){ //如果走到的点在范围中,继续向下搜索dfs(a,b,u+1,sum*10+g[a][b]); }}
}
int main(){cin>>n>>m>>k;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>g[i][j];}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){dfs(i,j,0,g[i][j]);}}cout<<se.size();return 0;
}
三、知识风暴
深搜DFS
- 尽量纵深搜索,可以利用栈或递归实现。
相关文章:
【蓝桥杯集训·每日一题】AcWing 3502. 不同路径数
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴一、题目 1、原题链接 3502. 不同路径数 2、题目描述 给定一个 nm 的二维矩阵,其中的每个元素都是一个 [1,9] 之间的正整数。 从矩阵中的任意位置出发…...

Java - 数据结构,二叉树
一、什么是树 概念 树是一种非线性的数据结构,它是由n(n>0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点: 1、有…...

模拟QQ登录-课后程序(JAVA基础案例教程-黑马程序员编著-第十一章-课后作业)
【案例11-3】 模拟QQ登录 【案例介绍】 1.案例描述 QQ是现实生活中常用的聊天工具,QQ登录界面看似小巧、简单,但其中涉及的内容却很多,对于初学者练习Java Swing工具的使用非常合适。本案例要求使用所学的Java Swing知识,模拟实…...

【壹】嵌入式系统硬件基础
随手拍拍💁♂️📷 日期: 2023.2.28 地点: 杭州 介绍: 日子像旋转毒马🐎,在脑海里转不停🤯 🌲🌲🌲🌲🌲 往期回顾 🌲🌲🌲…...

当参数调优无法解决kafka消息积压时可以这么做
今天的议题是:如何快速处理kafka的消息积压 通常的做法有以下几种: 增加消费者数增加 topic 的分区数,从而进一步增加消费者数调整消费者参数,如max.poll.records增加硬件资源 常规手段不是本文的讨论重点或者当上面的手段已经使…...

Java线程池源码分析
Java 线程池的使用,是面试必问的。下面我们来从使用到源码整理一下。 1、构造线程池 通过Executors来构造线程池 1、构造一个固定线程数目的线程池,配置的corePoolSize与maximumPoolSize大小相同, 同时使用了一个无界LinkedBlockingQueue存…...

手撕八大排序(下)
目录 交换排序 冒泡排序: 快速排序 Hoare法 挖坑法 前后指针法【了解即可】 优化 再次优化(插入排序) 迭代法 其他排序 归并排序 计数排序 排序总结 结束了上半章四个较为简单的排序,接下来的难度将会大幅度上升&…...

SAP 详细解析SCC4
事务代码:SCC4,选择一个客户端,点击进入,如图: 一、客户端角色 客户控制:客户的角色(生产性,测试,...) 此属性表示 R/3 系统中的客户端角色。其中可能包括…...

java异常分类和finally代码块中return语句的影响
首先看一下java中异常相关类的继承关系: 引用 1、分类 异常可以分为受查异常和非受查异常,Error和RuntimeException及其所有的子类都是非受查异常,其他的是受查异常。 两者的区别主要在: 受检的异常是由编译器(编译…...

【链表OJ题(二)】链表的中间节点
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯长路漫漫浩浩,万事皆有期待 文章目录链表OJ题(二)1. 链表…...

【强烈建议收藏:MySQL面试必问系列之并发事务锁专题】
一.知识回顾 上节课我们一起学习了MySQL面试必问系列之事务,没有学习的同学可以看一下上一篇文章,肯定对你会有帮助,学习过的同学肯定知道,上节课我们留了一个小尾巴,这个小尾巴是什么呢?就是没有详细展开…...

Linux下使用Makefile实现条件编译
在Linux系统下Makefile和C/C语言都有提供条件选择编译的语法,就是在编译源码的时候,可以选择性地编译指定的代码。这种条件选择编译的使用场合有好多,例如我们开发一个兼容标准版本与定制版本兼容的项目,那么,一些与需…...

java 应用cpu飙升(超过100%)故障排查
前言害。。。昨天刚写完一份关于jvm问题排查相关的博客,今天线上项目就遇到了一个突发问题。现象是用户反映系统非常卡,无法操作。然后登录服务器查看发现cpu 一直100%以上。具体排查步骤:1,首先top命令查看服务器cpu等情况&#…...

光学设计软件Ansys的Lumerical 2023版本下载与安装使用
文章目录前言一、许可管理工具安装二、许可管理器配置三、Lumerical安装四、工具使用配置总结前言 Lumerical是一款功能强大的软件,用于设计和分析从组件到系统阶段的光子学和电磁学。这个版本的Lumerical改进了电子和光子学设计工具,用于复杂光子学&am…...

Java 异常
文章目录1. 异常概述2. JVM 的默认处理方案3. 异常处理之 try...catch4. Throwable 的成员方法5. 编译异常和运行异常的区别6. 异常处理之 throws7. 自定义异常8. throws 和 throw 的区别1. 异常概述 异常就是程序出现了不正常的情况。 ① Error:严重问题ÿ…...

JavaSE学习笔记day17
零、 复习昨日 File: 通过路径代表一个文件或目录 方法: 创建型,查找类,判断类,其他 IO 输入& 输出字节&字符 try-catch代码 一、作业 给定路径删除该文件夹 public static void main(String[] args) {deleteDir(new File("E:\\A"));}// 删除文件夹public s…...

【项目】Vue3+TS 动态路由 面包屑 查询重置 列表
💭💭 ✨:【项目】Vue3TS 动态路由 面包屑 查询重置 列表 💟:东非不开森的主页 💜: 热烈的不是青春,而是我们💜💜 🌸: 如有错误或不足之处࿰…...
前脚背完这些接口自动化测试面试题,后脚就进了字节测试岗
1、请结合你熟悉的项目,介绍一下你是怎么做测试的? -首先要自己熟悉项目,熟悉项目的需求、项目组织架构、项目研发接口等 -功能 接口 自动化 性能 是怎么处理的? -第一步: 进行需求分析,需求评审&#…...
termux 安装centos
相关链接 centos官网rootfs制作其他人提供的安装脚本centos镜像列表其他人提供的安装脚本的说明 如果想使用老版本的centos7跟着上面链接5走就行 如果想用新系统比如centos9 stream,就跟我来 Q:为什么要装新系统? A:旧系统太多软件已过时,升级费时费…...

从菜鸟程序员到高级架构师,竟然是因为这个字final
final实现原理 简介 final关键字,实际的含义就一句话,不可改变。什么是不可改变?就是初始化完成之后就不能再做任何的修改,修饰成员变量的时候,成员变量变成一个常数;修饰方法的时候,方法不允…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...

LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...

【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...