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

【蓝桥杯集训·每日一题】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 的二维矩阵&#xff0c;其中的每个元素都是一个 [1,9] 之间的正整数。 从矩阵中的任意位置出发&#xf…...

Java - 数据结构,二叉树

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

模拟QQ登录-课后程序(JAVA基础案例教程-黑马程序员编著-第十一章-课后作业)

【案例11-3】 模拟QQ登录 【案例介绍】 1.案例描述 QQ是现实生活中常用的聊天工具&#xff0c;QQ登录界面看似小巧、简单&#xff0c;但其中涉及的内容却很多&#xff0c;对于初学者练习Java Swing工具的使用非常合适。本案例要求使用所学的Java Swing知识&#xff0c;模拟实…...

【壹】嵌入式系统硬件基础

随手拍拍&#x1f481;‍♂️&#x1f4f7; 日期: 2023.2.28 地点: 杭州 介绍: 日子像旋转毒马&#x1f40e;&#xff0c;在脑海里转不停&#x1f92f; &#x1f332;&#x1f332;&#x1f332;&#x1f332;&#x1f332; 往期回顾 &#x1f332;&#x1f332;&#x1f332…...

当参数调优无法解决kafka消息积压时可以这么做

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

Java线程池源码分析

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

手撕八大排序(下)

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

SAP 详细解析SCC4

事务代码&#xff1a;SCC4&#xff0c;选择一个客户端&#xff0c;点击进入&#xff0c;如图&#xff1a; 一、客户端角色 客户控制&#xff1a;客户的角色&#xff08;生产性&#xff0c;测试&#xff0c;...&#xff09; 此属性表示 R/3 系统中的客户端角色。其中可能包括…...

java异常分类和finally代码块中return语句的影响

首先看一下java中异常相关类的继承关系&#xff1a; 引用 1、分类 异常可以分为受查异常和非受查异常&#xff0c;Error和RuntimeException及其所有的子类都是非受查异常&#xff0c;其他的是受查异常。 两者的区别主要在&#xff1a; 受检的异常是由编译器&#xff08;编译…...

【链表OJ题(二)】链表的中间节点

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录链表OJ题(二)1. 链表…...

【强烈建议收藏:MySQL面试必问系列之并发事务锁专题】

一.知识回顾 上节课我们一起学习了MySQL面试必问系列之事务&#xff0c;没有学习的同学可以看一下上一篇文章&#xff0c;肯定对你会有帮助&#xff0c;学习过的同学肯定知道&#xff0c;上节课我们留了一个小尾巴&#xff0c;这个小尾巴是什么呢&#xff1f;就是没有详细展开…...

Linux下使用Makefile实现条件编译

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

java 应用cpu飙升(超过100%)故障排查

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

光学设计软件Ansys的Lumerical 2023版本下载与安装使用

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

Java 异常

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

JavaSE学习笔记day17

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

【项目】Vue3+TS 动态路由 面包屑 查询重置 列表

&#x1f4ad;&#x1f4ad; ✨&#xff1a;【项目】Vue3TS 动态路由 面包屑 查询重置 列表   &#x1f49f;&#xff1a;东非不开森的主页   &#x1f49c;: 热烈的不是青春&#xff0c;而是我们&#x1f49c;&#x1f49c;   &#x1f338;: 如有错误或不足之处&#xff0…...

前脚背完这些接口自动化测试面试题,后脚就进了字节测试岗

1、请结合你熟悉的项目&#xff0c;介绍一下你是怎么做测试的&#xff1f; -首先要自己熟悉项目&#xff0c;熟悉项目的需求、项目组织架构、项目研发接口等 -功能 接口 自动化 性能 是怎么处理的&#xff1f; -第一步&#xff1a; 进行需求分析&#xff0c;需求评审&#…...

termux 安装centos

相关链接 centos官网rootfs制作其他人提供的安装脚本centos镜像列表其他人提供的安装脚本的说明 如果想使用老版本的centos7跟着上面链接5走就行 如果想用新系统比如centos9 stream&#xff0c;就跟我来 Q:为什么要装新系统? A:旧系统太多软件已过时&#xff0c;升级费时费…...

从菜鸟程序员到高级架构师,竟然是因为这个字final

final实现原理 简介 final关键字&#xff0c;实际的含义就一句话&#xff0c;不可改变。什么是不可改变&#xff1f;就是初始化完成之后就不能再做任何的修改&#xff0c;修饰成员变量的时候&#xff0c;成员变量变成一个常数&#xff1b;修饰方法的时候&#xff0c;方法不允…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

【 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、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...