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

华为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列的二维矩阵&#xff0c;矩阵中每个位置的数字取值为0或1。矩阵示例如&#xff1a; 1100 0001 0011 1111 现需要将矩阵中所有的1进行反转为0&#xff0c;规则如下&#xff1a; 1&#xff09; 当点击一个1时&#xff0c;该1便被反转为…...

txt去重

目录 txt去重 让我解释一下代码的逻辑&#xff1a; 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 …...

系统集成测试与验收

功能性测试&#xff1a;测试系统应提供的每一个功能和安全性限制&#xff0c;检查系统是否已 正常实现所有功能。 连通性测试&#xff1a;测试网络上任意站点间是否能够相互传输数据&#xff0c;测试各个终端 能否登录中心服务器&#xff0c;并访问数据库&#xff0c;对数据库…...

ElementPlus文件上传 ,在上传前钩子中判断文件是否为图片

在ElementPlus中&#xff0c;可以使用beforeUpload属性来指定上传文件之前的钩子函数&#xff0c;在该函数中可以对文件进行判断并进行相关操作。 首先&#xff0c;在data中定义一个isImage变量来记录文件是否为图片&#xff0c;初始值为false。然后&#xff0c;在钩子函数中判…...

涂鸦智能获Matter Non-VID Scoped PAA资质 助力开发者拥抱Matter生态

今年5月&#xff0c;全球化IoT开发者平台涂鸦智能&#xff08;NYSE: TUYA&#xff0c;HKEX: 2391&#xff09;正式生成Tuya Matter PAA密钥根&#xff0c;并于7月&#xff0c;成功通过了连接标准联盟和第三方MA机构审查而上线。自此&#xff0c;涂鸦正式成为全球同时提供支持Ma…...

nsqd的架构及源码分析

文章目录 一 nsq的整体代码结构 二 回顾nsq的整体架构图 三 nsqd进程的作用 四 nsqd启动流程的源码分析 五 本篇博客总结 在博客 nsq整体架构及各个部件作用详解_YZF_Kevin的博客-CSDN博客 中我们讲了nsq的整体框架&#xff0c;各个部件的大致作用。如果没看过的&…...

​LeetCode解法汇总344. 反转字符串

目录链接&#xff1a; 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目&#xff1a; https://github.com/September26/java-algorithms 原题链接&#xff1a;力扣 描述&#xff1a; 编写一个函数&#xff0c;其作用是将输入的字符串反转过来。输入字符串以字符数…...

【C语言基础】数组的高级应用(上)

文章目录 一、数组的概念1.1 基本理解1.2 从内存角度理解数组1.3 从编译器角度理解数组 二、数组的定义2.1 第一种&#xff1a;完全初始化2.2 第二种&#xff1a;不完全初始化 三、访问数组的两种方式3.1 第一种&#xff1a;数组的方式依次访问3.2 第二种&#xff1a;指针的方式…...

面试题:bind、call、apply 区别?如何实现一个 bind?

面试题&#xff1a;bind、call、apply 区别&#xff1f;如何实现一个 bind? 一、call()代码描述&#xff1a; 二、apply()代码描述&#xff1a; 三、bind()—最重要代码描述&#xff1a; 四、call、apply、bind 总结 一、call() 代码描述&#xff1a; 二、apply() 代码描述&am…...

【SpringBoot学习笔记】01.第一个程序HelloWorld

项目创建方式&#xff1a;使用 IDEA 直接创建项目 1、创建一个新项目 2、选择spring initalizr &#xff0c; 可以看到默认就是去官网的快速构建工具那里实现 3、填写项目信息 4、选择初始化的组件&#xff08;初学勾选 Web 即可&#xff09; 5、填写项目路径 6、等待项目…...

【学会动态规划】买卖股票的最佳时机含手续费(16)

目录 动态规划怎么学&#xff1f; 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后&#xff1a; 动态规划怎么学&#xff1f; 学习一个算法没有捷径&#xff0c;更何况是学习动态规划&#xff0c; 跟我…...

网络原因导致git下载报错处理办法

如下&#xff0c;git clone时报错&#xff1a; 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后端选择什么服务器

对于很多刚入行的朋友来说&#xff0c;不清楚应该选择什么样的服务器提供商&#xff0c;是选择传统的IDC, 租用服务器租用机柜&#xff0c;还是选择现在很火的云服务器呢&#xff1f;在本文中&#xff0c;通过对比传统的IDC和云服务&#xff0c;简单阐述一下服务器的选择。  …...

什么是反射机制,反射机制的应用场景

文章目录 反射机制介绍获取 Class 对象的四种方式代码实例静态编译和动态编译反射机制优缺点反射的应用场景 反射机制介绍 JAVA 反射机制是在运行状态中&#xff0c;对于任意一个类&#xff0c;都能够知道这个类的所有属性和方法&#xff1b;对于任意一个对象&#xff0c;都能…...

Visual Studio 2019 实用功能设置(背景颜色,代码字体及行号设置)

前言 Visual Studio 2019 安装包的下载教程、安装教程 教程 博主博客链接&#xff1a;https://blog.csdn.net/m0_74014525 关注博主&#xff0c;后期持续更新系列文章 系列文章 第一篇&#xff1a;Visual Studio 2019 详细安装教程&#xff08;图文版&#xff09; 第二篇&…...

简述Mysql索引

一、索引概述 1.1 索引概述 MySQL官方对索引的定义为&#xff1a;索引&#xff08;Index&#xff09;是帮助MySQL高效获取数据的数据结构。 索引的本质&#xff1a;索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”&#xff0c;满足特定查找算法。 这些数据结…...

windows .gitignore 加入文件名后 依然可以从git status中看到文件问题

最近在学git&#xff0c;对着b站的视频操作&#xff0c;结果很简单的添加.gitignore文件操作&#xff0c;up主的正常隐藏&#xff0c;我的却一直出问题。 百思不得其解&#xff0c;网上各种啥啥啥清缓存都没讲到点上。 最后发现是.gitignore文件有问题&#xff0c;windows默认…...

召唤神龙打造自己的ChatGPT

在之前的两篇文章中&#xff0c;我介绍了GPT 1和2的模型&#xff0c;并分别用Tensorflow和Pytorch来实现了模型的训练。具体可以见以下文章链接&#xff1a; 1. 基于Tensorflow来重现GPT v1模型_gzroy的博客-CSDN博客 2. 花费7元训练自己的GPT 2模型_gzroy的博客-CSDN博客 有…...

裝修公司同室內設計公司有咩分別?

很多裝修業主都會有裝修公司師傅會不會「出圖」的這個疑問。 出圖是指室內設計的各種圖&#xff0c;是設計師跟戶主和裝修師傅溝通裝修的工具&#xff0c;亦都係施工、驗收的證明。通常齊全的圖通常只有設計公司才可以完整提供例如平面圖、3D效果圖等等。 由於室內設計公司會…...

android oaid

Oaid获取接入流程 移动智能设备标识公共服务平台 AndroidID、IMEI、OAID获取 oaid_sdk_1.1.0的aar 随着Google对隐私的重视以及Android10的逐渐普及&#xff0c;获取设备的唯一标识越来越来难&#xff0c;在Android10以前&#xff0c;Android设备唯一标识包含IMEI、AndroidID、…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...