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

开心消消乐

给定一个 N 行 M 列的二维矩阵,矩阵中每个位置的数字取值为 0 或 1,矩阵示例如:

1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1

现需要将矩阵中所有的 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

输出

示例二

输入

4 4
1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1

输出

2

说明:第一个元素是1,点击后,右侧也是1,所以第一次点击紫色的1会置为0,当遍历到第二行最后一个元素时,发现该位置是1,则搜索它的周围位置,如果是1,置为0,然后继续搜索刚刚置为0的位置的周边位置,依次循环,则红色的1一次被置为0

1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1

解题思路:遍历二维数组,遇到某个位置的值为1,则开始查找它周围8个方向的位置的值,如果是1,置为0。然后继续遍历下一个元素。使用DFS算法。

读取输入数据代码略,直接使用定义好的数组。

Java代码,以用例二为例

    public static void main(String[] args) {int[][] arr = {{1,1,0,0},{0,0,0,1},{0,0,1,1},{1,1,1,1}};int count = 0;for(int i=0;i<arr.length;i++){for(int j=0;j<arr[0].length;j++){if (arr[i][j] == 0){continue;}//遇到 1 开始搜索,计数加 1dfs(arr,i,j);count++;}}System.out.println(count);}private static void dfs(int[][] arr,int row,int col){//如果索引越界,退出if (row<0||col<0||row>arr.length-1||col>arr[0].length-1){return;}//如果某个位置值为 1if (arr[row][col] == 1){//置为0arr[row][col] = 0;//左dfs(arr,row-1,col);//右dfs(arr,row+1,col);//上dfs(arr,row,col-1);//下dfs(arr,row,col+1);//右下dfs(arr,row+1,col+1);//左上dfs(arr,row-1,col-1);//右上dfs(arr,row+1,col-1);//左下dfs(arr,row-1,col+1);}}

相关文章:

开心消消乐

给定一个 N 行 M 列的二维矩阵&#xff0c;矩阵中每个位置的数字取值为 0 或 1&#xff0c;矩阵示例如&#xff1a; 1 1 0 0 0 0 0 1 0 0 1 1 1 1 1 1 现需要将矩阵中所有的 1 进行反转为 0&#xff0c;规则如下&#xff1a; 当点击一个 1 时&#xff0c;该 1 被反转为 0&am…...

有效日志管理在软件开发和运营中的作用

作者&#xff1a;Luca Wintergerst, David Hope, Bahubali Shetti 当今存在的快速软件开发过程需要扩展和复杂的基础架构和应用程序组件&#xff0c;并且操作和开发团队的工作不断增长且涉及多个方面。 有助于管理和分析遥测数据的可观察性是确保应用程序和基础架构的性能和可靠…...

【五一创作】【笔记】Git|如何将仓库中所有的 commit 合成一个?又名,如何清除所有 git 提交记录?(附 git rebase 机制的简要分析)

在对代码进行开源时&#xff0c;我们往往并不希望代码开发过程中的提交记录被其他人看到&#xff0c;因为提交的过程中往往会涵盖一些敏感信息。因此会存在 将仓库中所有 commit 合成一个 的需求。 直觉上&#xff0c;往往会用 rebase 和 squash 或 reset&#xff0c;不过我尝…...

如何写出高质量代码?

作为一名资深开发人员&#xff0c;写出高质量的代码是我们必须要追求的目标。然而&#xff0c;在实际开发中&#xff0c;我们常常会遇到各种问题。比如&#xff0c;代码的可读性、可维护性、健壮性和灵活性等&#xff0c;这些都会影响代码的质量。那么&#xff0c;究竟如何才能…...

外卖项目优化-01-redis缓存短信验证码、菜品数据、Spring Cache(注解开发缓存)、(注解开发)缓存套餐数据

文章目录 外卖项目优化-01课程内容前言1. 环境搭建1.1 版本控制解决branch和tag命名冲突 1.2 环境准备 2. 缓存短信验证码2.1 思路分析2.2 代码改造2.3 功能测试 3. 缓存菜品信息3.1 实现思路3.2 代码改造3.2.1 查询菜品缓存3.2.2 清理菜品缓存 3.3 功能测试3.4 提交并推送代码…...

Chapter1:控制系统数学模型(下)

第一章:控制系统数学模型 Exercise1.13 已知控制系统结构图如下图所示,求系统的输出 C 1 ( s ) C_1(s) C...

排序算法总结

常见排序算法的时间复杂度、空间复杂度及稳定性分析&#xff1a; 时间复杂度空间复杂度是否有稳定性基于比较的排序算法选择排序 O(N^2)O(1)否 冒泡排序O(N^2)O(1)是插入排序O(N^2)O(1)是归并排序O(N*logN)O(N)&#xff0c;每次需要额外一个数组用于拷贝是快排O(N*log…...

java+jsp企业物流货运快递管理系统servlet

功能需求具体描述&#xff1a; (1)用户功能模块包括用户登录注册&#xff0c;用户信息的修改&#xff0c;用户发布货物信息&#xff0c;给客服人员留言&#xff0c;对运输公司进行评价。 (2)企业功能模块包括企业注册登录&#xff0c;企业信息的修改&#xff0c;受理用户发布的…...

【ROS仿真实战】获取机器人在gazebo位置真值的三种方法(三)

文章目录 前言一. 使用ROS tf库二、 使用Gazebo Model Plugin三、 使用libgazebo_ros_p3d插件四、总结 前言 在ROS和Gazebo中&#xff0c;获取机器人的位置信息通常通过ROS消息传递进行。在这篇文章中&#xff0c;我们将介绍三种获取机器人在Gazebo中位置真值的方法&#xff1…...

Winform从入门到精通(35)——FontDialog(史上最全)

文章目录 前言一、属性1、Name2、AllowScriptChange3、AllowSimulations4、AllowVectorFonts5、AllowVerticalFonts6、Color7、FixedPitchOnly8、Font9、FontMustExist10、MaxSize11、MinSize12、 ScriptsOnly13、ShowApply14、ShowColor15、ShowEffects16、ShowHelp...

AcWing 854. Floyd求最短路Floyd模板

Floyd算法&#xff1a; 标准弗洛伊德算法&#xff0c;三重循环&#xff0c;基于动态规划。 循环结束之后 d[i][j]存储的就是点 i 到点 j 的最短距离。 需要注意循环顺序不能变&#xff1a;第一层枚举中间点&#xff0c;第二层和第三层枚举起点和终点。 特点&#xff1a; 1.复杂…...

Graph Theory(图论)

一、图的定义 图是通过一组边相互连接的顶点的集合。 In this graph, V { A , B , C , D , E } E { AB , AC , BD , CD , DE } 二、图的类型 2.1 Finite Graph A graph consisting of finite number of vertices and edges is called as a finite graph. Null Graph Tri…...

[Python]生成 txt 文件

前段时间有位客户问: 你们的程序能不能给我们生成个 txt 文件,把新增的员工都放进来,字段也不需要太多,就要 员工姓名/卡号/员工编号/员工职位/公司 这些字段就行了,然后我们的程序会去读取这个 txt 文件,拿里面的内容,读完之后会这个文件删掉 我: 可以接受延迟吗?可能没办法实…...

GeoTools实战指南: 自定义矢量样式并生成截图

GeoTools实战指南: 自定义矢量样式并生成截图 介绍 本段代码的主要功能是将矢量数据(Shapefile)渲染成一张图片。 准备环境 首先,您需要将GeoTools库添加到您的项目中。使用Maven或Gradle添加依赖项,或者直接下载GeoTools的jar文件并添加到您的类路径中。 Maven <…...

深度学习超参数调整介绍

文章目录 深度学习超参数调整介绍1. 学习率2. 批大小3. 迭代次数4. 正则化5. 网络结构总结 深度学习超参数调整介绍 深度学习模型的性能很大程度上取决于超参数的选择。超参数是指在训练过程中需要手动设置的参数&#xff0c;例如学习率、批大小、迭代次数、网络结构等等。选择…...

Bootloader

本篇不作太过的技术了解&#xff0c;仅可作为初学者的参考。用嘴简单的语言讲清楚一件事。 项目中遇到Bootloader升级MCU&#xff0c;我很好这是什么软件&#xff0c;逻辑是什么&#xff0c;怎么升级的。 术语及定义 指纹信息fingerprint诊断仪用于标识特定的下载尝试的信息 …...

安卓开发_广播机制_广播的最佳实践:实现强制下线功能

安卓开发_广播机制_广播的最佳实践&#xff1a;实现强制下线功能 ActivityCollector类用于管理所有的ActivityBaseActivity类作为所有Activity的父类创建一个LoginActivity来作为登录界面布局LoginActivity 在MainActivity中加入强制下线功能布局MainActivity在BaseActivity中注…...

国民技术N32G430开发笔记(10)- IAP升级 Application 的制作

IAP升级 Application 的制作 1、App程序跟Bootloader程序最大的区别就是&#xff0c; 程序的执行地址变成了之前flash设定的0x08006000处&#xff0c; 大小限制为20KB 所以修改Application工程的ld文件 origin 改成 0x08006000 length 改成0x5000 烧录是起始地址也要改为x0x…...

[计算机图形学]材质与外观(前瞻预习/复习回顾)

一、图形学中的材质 不同的物体表面有着不同的材质&#xff0c;而不同的材质意味着它们与光线的作用不同。那么我们之前在介绍辐射度量学和渲染方程提到过其中一个函数&#xff0c;叫做BRDF&#xff0c;而在实际上&#xff0c;也就是BRDF定义了不同的材质。BRDF决定了光如何被反…...

Java 的简要介绍及开发环境的搭建(超级详细)

图片来源于互联网 目录 | CONTENT Java 简介 一、什么是 Java 二、认识 Java 版本 三、选择哪个版本比较好 搭建 Java 开发环境 一、下载 Java 软件开发工具包 JDK 二、配置环境变量 自动配置 手动配置 三、下载合适的 IDE IntelliJ IDEA Visual Studio Code Eclip…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...