【华为OD机试真题】【2024年E卷】数值同化-队列BFS(C++/Java/Python)
文章目录
- 分值:200
- 题目描述
- 思路
- 复杂度分析
- AC 代码
分值:200
题目描述
存在一个 m * n 的 二维数组只,其成员取值范围为0, 1, 2。其中值为1的元素具备同化特性,每经过1S,将上下左右值为0的元素同化为1。而值为2的元素,免疫同化。
将数组所有成员随机初始化只为0或2,再将矩阵的[0,0]元素修改成1,在经过足够长的时间后,求矩阵中有多少个元素是0或2(即0和2数量之和)。
输入描述:
输入的前两个数字是矩阵大小n 和m。
接着输入n行m列,表示矩阵信息。
输出描述:
返回矩阵中非 1的元素个数。
示例1
输入:
4 4
0 0 0 0
0 2 0 0
0 0 2 0
0 0 0 2
输出:
3
解释:
除了矩阵中 3 个值为2的元素,其他元素全部同化为1了。
示例2
输入:
4 4
0 2 0 0
0 2 0 0
0 2 0 0
0 2 0 0
输出:
12
解释:
只有第一列被同化为1了,第2、3、4列没有被同化,因为第二列全是值为2的元素,阻挡住同化了。
Tips:
0 < m, n <= 30
思路
- 从将上下左右值为
0的元素同化为1这点可以联系到BFS,这是一道很经典的宽度优先搜索的题目,可以当做模板题进行练习。 - 从
[0, 0]开始出发,只有值为0的元素才能被同化,所以只将1周围的0元素放进队列,直到队列为空即可。 - 答案要求返回矩阵中
非 1的元素个数。可以在遍历的同时进行计算,每当有一个元素被同化,那么ans就减一。
复杂度分析
- 时间复杂度: O ( n ∗ m ) O(n*m) O(n∗m),其中
N和M分别为矩阵的行长跟列长,每个位置只需要访问一次。 - 空间复杂度: O ( n ∗ m ) O(n*m) O(n∗m),其中
N和M分别为矩阵的行长跟列长,用于存储矩阵信息。
AC 代码
C++ 版
#include <bits/stdc++.h>
using namespace std;
int main()
{int n, m, ans, dis[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};cin >> n >> m;vector<vector<int>> mx(n, vector<int>(m));for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> mx[i][j];}}mx[0][0] = 1;// 一开始 0 跟 2 的个数之和, 后面每次有同化的就 -1 即可ans = n * m - 1;queue<pair<int, int>> q;q.push({0, 0});while (!q.empty()){auto t = q.front();q.pop();for (int i = 0; i < 4; i++){int x = t.first + dis[i][0], y = t.second + dis[i][1];if (x >= 0 && x < n && y >= 0 && y < m && mx[x][y] == 0){mx[x][y] = 1;ans--;q.push({x, y});}}}cout << ans << endl;return 0;
}
JAVA 版
import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int ans;int[][] dis = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int[][] mx = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {mx[i][j] = scanner.nextInt();}}mx[0][0] = 1;ans = n * m - 1;Queue<int[]> q = new LinkedList<>();q.add(new int[]{0, 0});while (!q.isEmpty()) {int[] t = q.poll();for (int i = 0; i < 4; i++) {int x = t[0] + dis[i][0];int y = t[1] + dis[i][1];if (x >= 0 && x < n && y >= 0 && y < m && mx[x][y] == 0) {mx[x][y] = 1;ans--;q.add(new int[]{x, y});}}}System.out.println(ans);}
}
Python 版
from collections import dequen, m = map(int, input().split())
ans = 0
dis = [[-1, 0], [1, 0], [0, -1], [0, 1]]mx = []
for _ in range(n):mx.append(list(map(int, input().split())))mx[0][0] = 1
ans = n * m - 1
q = deque([(0, 0)])while q:t = q.popleft()for i in range(4):x = t[0] + dis[i][0]y = t[1] + dis[i][1]if 0 <= x < n and 0 <= y < m and mx[x][y] == 0:mx[x][y] = 1ans -= 1q.append((x, y))print(ans)
相关文章:
【华为OD机试真题】【2024年E卷】数值同化-队列BFS(C++/Java/Python)
文章目录 分值:200题目描述思路复杂度分析AC 代码 分值:200 题目描述 存在一个 m * n 的 二维数组只,其成员取值范围为0, 1, 2。其中值为1的元素具备同化特性,每经过1S,将上下左右值为0的元素同化为1。而值为2的元素…...
“魔法糖果盒的秘密:用朴素贝叶斯算法猜糖果颜色”
想象一下,你有一个神奇的糖果盒,这个糖果盒里有两种糖果:红色的和蓝色的。你闭上眼睛,从盒子里拿出一个糖果,然后尝一尝,你想知道这个糖果是红色的还是蓝色的。朴素贝叶斯算法就像是一个魔法规则࿰…...
linux中docker命令大全
基本命令 docker pull 拉取镜像 docker pull docker push 推送镜像到DockerRegistry docker push docker images 查看本地镜像 docker images docker rmi 删除本地镜像 docker rmi docker run 创建并运行容器(不能重复创建) docker run d…...
Python `str.strip()` 的高级用法详解
Python str.strip 的高级用法详解 1. str.strip() 的基本用法2. str.strip() 的高级用法2.1 移除指定字符2.2 移除多个指定字符2.3 移除换行符和制表符2.4 结合正则表达式的高级处理 3. lstrip() 和 rstrip() 的用法3.1 lstrip():移除左端字符3.2 rstrip()ÿ…...
[蓝桥杯 2019 国 B] 排列数
目录 前言 题解 思路 疑问 解答 前言 对于本篇文章是站在别人的基础之上来写的,对于这道题作为2019年国赛B组的最难的一题,他的难度肯定是不小的,这道题我再一开始接触的时候连思路都没有,也是看了两三遍别人发的题解&#x…...
[bug] StarRocks borker load意向之外的bug
意向之外,又清理之中 背景: StarRocks各方面碾压相同类型的数据库,最近我们要从生成HIVE导历史数据(ORC格式)到StarRocks,前期小测一下,在测试是没问题,上生产先导2个月的数据&…...
2025年前端面试热门题目——HTML|CSS|Javascript|TS知识
以下是对这些 HTML 面试问题的详细解答: 1. HTML 的 src 和 href 属性有什么区别? src (Source) 属性: 用于嵌入资源,例如图像、脚本或 iframe。加载资源时,当前页面的加载会暂停,直到资源加载完成。常用于 <img&g…...
Linux中部署项目
1.下载JDK17 进入 /usr/local 目录,创建 java 文件夹。并将 JDK17 上传到 java 目录下。 上传成功后,通过cd命令进入Java文件夹目录,解压 JDK17 压缩包,命令 unzip zulu17.44.53-ca-jdk17.0.8.1-linux_x64.zip。 如果报错说 u…...
在 CentOS 上安装 MySQL 8
在 CentOS 上安装 MySQL 8 您可以按照以下步骤操作: 1. 更新系统 首先,更新系统软件包以确保安装的最新版本。 sudo yum update -y 2. 安装 MySQL 8 安装 MySQL 存储库 wget https://dev.mysql.com/get/mysql80-community-release-el7-3.noarch.r…...
gradle项目下载依赖报错
报错信息 Cannot resolve external dependency org.projectlombok:lombok:1.18.36 because no repositories are defined. Required by:project :Possible solution:- Declare repository providing the artifact, see the documentation at https://docs.gradle.org/current/…...
solon 集成 activemq-client (sdk)
原始状态的 activemq-client sdk 集成非常方便,也更适合定制。就是有些同学,可能对原始接口会比较陌生,会希望有个具体的示例。 <dependency><groupId>org.apache.activemq</groupId><artifactId>activemq-client&l…...
LRU 缓存
LRU 缓存 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类: LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否…...
使用ZLMediaKit 开源项目搭建RTSP 服务器
ZLMediaKit 是啥? ZLMediaKit是国人开发的开源C流媒体服务器,同SRS一样是主流的流媒体服务器。 ZLToolKit是基于C11的高性能服务器框架,和ZLMediaKit是同一个作者,ZLMediaKit正是使用该框架开发的。 官网 ZLMediaKit开源地址&…...
数组晨考2day08
1.用一句话描述数组 在内存中 一块连续的空间 存储相同类型的数据 长度是固定的 2.数组各个类型的默认值 整数:0 浮点:0.0 布尔:false 字符:\u0000 其他:null 3.Arrays类toString,copyOf,sort&a…...
《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》简介
《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》已于近日上市,该书由北京大学出版社出版。距离第1版上市已经过去二年半多。本文希望与读者朋友们分享下这本书里面的大致内容。 封面部分 首先是介绍封面部分。 《鸿蒙HarmonyOS应用开发从入门…...
麒麟操作系统服务架构保姆级教程(二)sersync、lsync备份和NFS持久化存储
如果你想拥有你从未拥有过的东西,那么你必须去做你从未做过的事情 上篇文章我们说到rsync虽好,但是缺乏实时性,在实际应用中,咱们可以将rsync写进脚本,然后写进定时任务去备份,如果每天凌晨1:00…...
将OBJ或GLB文件转换为3DTiles
格式简介 GLB文件(.GLB)代表“GL传输格式二进制文件”,是用于共享3D数据的标准化文件格式。确切地说,它可以包含有关三维模型、场景、模型、光源、材质、节点层次和动画的信息。 OBJ文件是一种文本文件格式,这就意味…...
Flink DataStream API 编程指南
(对于Flink的开发,建议使用Java,Scala的支持未来会被移除) DataStream是什么 DataStream API得名于DataStream这个Java类,可以将它们视为可以包含重复项的不可变数据集合。该数据可以是有限的,也可以是无限的,用于处理它们的API是相同的。 DataStream在用法上和普通的…...
tryhackme-Pre Security-HTTP in Detail(HTTP的详细内容)
任务一:What is HTTP(S)?(什么是http(s)) 1.What is HTTP? (HyperText Transfer Protocol)(什么是 HTTP?(超文本传输协议)) http是你查看网站的时候遵循的…...
探索 Plotly:一个强大的交互式数据可视化库
探索 Plotly:一个强大的交互式数据可视化库 数据可视化是数据分析过程中不可或缺的一部分,它能帮助我们更直观地理解数据,发现数据中的趋势和规律。在众多可视化库中,Plotly 是一个非常强大的工具,它以其交互式、易用…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
第7篇:中间件全链路监控与 SQL 性能分析实践
7.1 章节导读 在构建数据库中间件的过程中,可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中,必须做到: 🔍 追踪每一条 SQL 的生命周期(从入口到数据库执行)&#…...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
