华为OD机试真题【开心消消乐】
1、题目描述
【开心消消乐】
给定一个N行M列的二维矩阵,矩阵中每个位置的数字取值为0或1。矩阵示例如:
1100
0001
0011
1111
现需要将矩阵中所有的1进行反转为0,规则如下:
1) 当点击一个1时,该1便被反转为0,同时相邻的上、下、左、右,以及左上、左下、右上、右下8 个方向的1(如果存在1)均会自动反转为0;
2)进一步地,一个位置上的1被反转为0时,与其相邻的8个方向的1(如果存在1)均会自动反转为0;
按照上述规则示例中的矩阵只最少需要点击2次后,所有值均为0。请问,给定一个矩阵,最少需要点击几次后,所有数字均为0?
【输入描述】
第一行输入两个整数,分别表示矩阵的行数 N 和列数 M,取值范围均为 [1,100]。接下来 N 行表示矩阵的初始值,每行均为 M 个数,取值范围 [0,1]。
【输出描述】
输出一个整数,表示最少需要点击的次数。
【实例一】
输入:
3 3
1 0 1
0 1 0
1 0 1
输出: 1,说明:上述样例中,四个角上的1均在中间的1的相邻8个方向上,因此只需要点击一次即可。
2、解题思路
此题与【岛屿数量】题类似,可用dfs回溯遍历的方法感染矩阵的位置即将符合题意的方向的1都变成0,统计需要多少次才能将矩阵中所有的值都变成0
3、参考代码
import java.util.Scanner;/*** @Author * @Date 2023/4/25 23:57*/
public class 开心消消乐 {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) {int n = in.nextInt();int m = in.nextInt();int[][] arr = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {arr[i][j] = in.nextInt();}}int res = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (arr[i][j] == 1) {infect(arr, i, j);res++;}}}System.out.println(res);}}public static void infect(int[][] arr, int x, int y) {if(x < 0 || y < 0 || x >= arr.length || y >= arr[0].length || arr[x][y] != 1) {return;}arr[x][y] = 0; // 感染的过程infect(arr, x + 1, y); // 向下infect(arr, x - 1, y); // 向上infect(arr, x, y + 1); // 向右infect(arr, x, y - 1); // 向左infect(arr, x + 1, y - 1); // 向左下infect(arr, x + 1, y + 1); // 向右上infect(arr, x + 1, y + 1); // 向右下infect(arr, x - 1, y + 1); // 向左上}
}
4、相似题目
(1)岛屿数量
区别在于这题指能向四个方向感染,而【开心消消乐】能向八个方向感染
public int numIslands(char[][] grid) {int count = 0;for(int i = 0; i < grid.length; i++) {for(int j = 0; j < grid[0].length; j++) {if(grid[i][j] == '1'){infect(grid, i, j);count++;}}}return count;}private void infect(char[][] grid, int i, int j){if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return;grid[i][j] = '0';infect(grid, i + 1, j); // 向下infect(grid, i, j + 1); // 向右infect(grid, i - 1, j); // 向上infect(grid, i, j - 1); // 向左}
相关文章:
华为OD机试真题【开心消消乐】
1、题目描述 【开心消消乐】 给定一个N行M列的二维矩阵,矩阵中每个位置的数字取值为0或1。矩阵示例如: 1100 0001 0011 1111 现需要将矩阵中所有的1进行反转为0,规则如下: 1) 当点击一个1时,该1便被反转为…...
txt去重
目录 txt去重 让我解释一下代码的逻辑: for a in [a.strip(\n) for a in list(f_read)]: txt去重 f_read open(r./1.txt, r, encodingutf-8) f_write open(r./2.txt, w,encodingutf-8) data set() for a in [a.strip(\n) for a in list(f_read)]:if a not in …...
系统集成测试与验收
功能性测试:测试系统应提供的每一个功能和安全性限制,检查系统是否已 正常实现所有功能。 连通性测试:测试网络上任意站点间是否能够相互传输数据,测试各个终端 能否登录中心服务器,并访问数据库,对数据库…...
ElementPlus文件上传 ,在上传前钩子中判断文件是否为图片
在ElementPlus中,可以使用beforeUpload属性来指定上传文件之前的钩子函数,在该函数中可以对文件进行判断并进行相关操作。 首先,在data中定义一个isImage变量来记录文件是否为图片,初始值为false。然后,在钩子函数中判…...
涂鸦智能获Matter Non-VID Scoped PAA资质 助力开发者拥抱Matter生态
今年5月,全球化IoT开发者平台涂鸦智能(NYSE: TUYA,HKEX: 2391)正式生成Tuya Matter PAA密钥根,并于7月,成功通过了连接标准联盟和第三方MA机构审查而上线。自此,涂鸦正式成为全球同时提供支持Ma…...
nsqd的架构及源码分析
文章目录 一 nsq的整体代码结构 二 回顾nsq的整体架构图 三 nsqd进程的作用 四 nsqd启动流程的源码分析 五 本篇博客总结 在博客 nsq整体架构及各个部件作用详解_YZF_Kevin的博客-CSDN博客 中我们讲了nsq的整体框架,各个部件的大致作用。如果没看过的&…...
LeetCode解法汇总344. 反转字符串
目录链接: 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目: https://github.com/September26/java-algorithms 原题链接:力扣 描述: 编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数…...
【C语言基础】数组的高级应用(上)
文章目录 一、数组的概念1.1 基本理解1.2 从内存角度理解数组1.3 从编译器角度理解数组 二、数组的定义2.1 第一种:完全初始化2.2 第二种:不完全初始化 三、访问数组的两种方式3.1 第一种:数组的方式依次访问3.2 第二种:指针的方式…...
面试题:bind、call、apply 区别?如何实现一个 bind?
面试题:bind、call、apply 区别?如何实现一个 bind? 一、call()代码描述: 二、apply()代码描述: 三、bind()—最重要代码描述: 四、call、apply、bind 总结 一、call() 代码描述: 二、apply() 代码描述&am…...
【SpringBoot学习笔记】01.第一个程序HelloWorld
项目创建方式:使用 IDEA 直接创建项目 1、创建一个新项目 2、选择spring initalizr , 可以看到默认就是去官网的快速构建工具那里实现 3、填写项目信息 4、选择初始化的组件(初学勾选 Web 即可) 5、填写项目路径 6、等待项目…...
【学会动态规划】买卖股票的最佳时机含手续费(16)
目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 动态规划怎么学? 学习一个算法没有捷径,更何况是学习动态规划, 跟我…...
网络原因导致git下载报错处理办法
如下,git clone时报错: RPC failed; curl 18 transfer closed with outstanding read data remaining 5670 bytes of body are still expected fetch-pack: unexpected disconnect while reading sideband packet early EOF fetch-pack: invalid index…...
APP后端选择什么服务器
对于很多刚入行的朋友来说,不清楚应该选择什么样的服务器提供商,是选择传统的IDC, 租用服务器租用机柜,还是选择现在很火的云服务器呢?在本文中,通过对比传统的IDC和云服务,简单阐述一下服务器的选择。 …...
什么是反射机制,反射机制的应用场景
文章目录 反射机制介绍获取 Class 对象的四种方式代码实例静态编译和动态编译反射机制优缺点反射的应用场景 反射机制介绍 JAVA 反射机制是在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法;对于任意一个对象,都能…...
Visual Studio 2019 实用功能设置(背景颜色,代码字体及行号设置)
前言 Visual Studio 2019 安装包的下载教程、安装教程 教程 博主博客链接:https://blog.csdn.net/m0_74014525 关注博主,后期持续更新系列文章 系列文章 第一篇:Visual Studio 2019 详细安装教程(图文版) 第二篇&…...
简述Mysql索引
一、索引概述 1.1 索引概述 MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。 索引的本质:索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”,满足特定查找算法。 这些数据结…...
windows .gitignore 加入文件名后 依然可以从git status中看到文件问题
最近在学git,对着b站的视频操作,结果很简单的添加.gitignore文件操作,up主的正常隐藏,我的却一直出问题。 百思不得其解,网上各种啥啥啥清缓存都没讲到点上。 最后发现是.gitignore文件有问题,windows默认…...
召唤神龙打造自己的ChatGPT
在之前的两篇文章中,我介绍了GPT 1和2的模型,并分别用Tensorflow和Pytorch来实现了模型的训练。具体可以见以下文章链接: 1. 基于Tensorflow来重现GPT v1模型_gzroy的博客-CSDN博客 2. 花费7元训练自己的GPT 2模型_gzroy的博客-CSDN博客 有…...
裝修公司同室內設計公司有咩分別?
很多裝修業主都會有裝修公司師傅會不會「出圖」的這個疑問。 出圖是指室內設計的各種圖,是設計師跟戶主和裝修師傅溝通裝修的工具,亦都係施工、驗收的證明。通常齊全的圖通常只有設計公司才可以完整提供例如平面圖、3D效果圖等等。 由於室內設計公司會…...
android oaid
Oaid获取接入流程 移动智能设备标识公共服务平台 AndroidID、IMEI、OAID获取 oaid_sdk_1.1.0的aar 随着Google对隐私的重视以及Android10的逐渐普及,获取设备的唯一标识越来越来难,在Android10以前,Android设备唯一标识包含IMEI、AndroidID、…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
