计算疫情扩散时间
该专栏题目包含两部分:
100 分值部分题目
200 分值部分题目
所有题目都会陆续更新,订阅防丢失
题目描述
在一个地图中(地图由 N ∗ N N*N N∗N 个区域组成),有部分区域被感染病菌。
感染区域每天都会把周围(上下左右)的4个区域感染。
请根据给定的地图计算,多少天以后,全部区域都会被感染。
如果初始地图上所有区域全部都被感染,或者没有被感染区域,返回-1
输入描述
-
行 N ∗ N N*N N∗N 个数字(只包含0,1,不会有其他数字)表示一个地图,数字间用","分割
-
0 表示未感染区域
-
1表示已经感染区域
每 N N N 个数字表示只地图中一行,输入数据共表示 N N N 行 N N N 列的区域地图。例如输入:
1,0,1,0,0,0,1,0,1
表示地图
[ 1 0 1 0 0 0 1 0 1 ] \begin{bmatrix} 1&0&1 \\ 0&0&0 \\ 1&0&1 \\ \end{bmatrix} 101000101
输出描述
1个整数,表示经过多少天以后,全部区域都被感染
数据范围
- 1 ≤ N < 200 1≤N<200 1≤N<200
示例1
输入
1.0,1 0.0,0,1.0,1
输出
2
说明
1天以后,地图中仅剩余中心点未被感染;2天以后,全部被感染。
示例2
输入
0,0,0,0
输出
-1
说明
无感染区域
示例3
输入
1,1,1,1,1,1,1,1,1
输出
-1
说明
全部都感染
题解
BFS 使用广度优先算法求解
源码 Java
import java.util.ArrayList;
import java.util.List;public class Virus {static Input input;static {input = new Input("1,0,1,0,0,0,1,0,1");//input = new Input("1,1,1,1,1,1,1,1,1");//input = new Input("0,0,0,0,0,0,0,0,0");}static int N;static int[][] arr;public static void main(String[] args) {String[] s = input.nextLine().split(",");int n = (int)Math.sqrt(s.length);N = n;arr = new int[n][n];int index = 0;List<Point> list = new ArrayList<>();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {int i1 = Integer.parseInt(s[index++]);if (1 == i1) {list.add(new Point(i, j));}arr[i][j] = i1;}}if (list.size() == 0 || list.size() == s.length){System.out.println(-1);} else {System.out.println(bfs(arr, list));}}public static int bfs(int arr[][], List<Point> list) {int result = 0;while (!list.isEmpty()) {result++;int size = list.size();List<Point> temp = new ArrayList<>();for (int i = 0; i < size; i++) {Point point = list.get(i);if (isCleanArea(point.x - 1, point.y)) {temp.add(new Point(point.x - 1, point.y));arr[point.x - 1][point.y] = 1;}if (isCleanArea(point.x + 1, point.y)) {temp.add(new Point(point.x + 1, point.y));arr[point.x + 1][point.y] = 1;}if (isCleanArea(point.x, point.y - 1)) {temp.add(new Point(point.x, point.y - 1));arr[point.x][point.y - 1] = 1;}if (isCleanArea(point.x, point.y + 1)) {temp.add(new Point(point.x, point.y + 1));arr[point.x][point.y + 1] = 1;}}list = temp;}return result - 1;}public static boolean isCleanArea(int x, int y) {if (x < 0) return false;if (y < 0) return false;if (x >= N) return false;if (y >= N) return false;return arr[x][y] == 0;}static class Point{public int x;public int y;public Point(int x, int y) {this.x = x;this.y = y;}}}
相关文章:
计算疫情扩散时间
该专栏题目包含两部分: 100 分值部分题目 200 分值部分题目 所有题目都会陆续更新,订阅防丢失 题目描述 在一个地图中(地图由 N ∗ N N*N N∗N 个区域组成),有部分区域被感染病菌。 感染区域每天都会把周围(上下左右)的4个区域感染。 请…...
【Windows11】24H2 内存占用高(截至10月31日)
文章目录 一、问题二、解决三、原因 一、问题 系统版本: 内存只有32GB。 以前只有我在运行数据处理程序的时候内存占用才会很高,日常情况下应该只有40%、50%左右的。 但是24H2,日常情况下内存占用80%以上。 而我只开了很少的应用&#…...
题目:多个字符从两端移动,向中间汇聚
【多个字符从两端移动,向中间汇聚】 char arr1[] "Good Good Study,Day Day Up!" ; char arr2[] "***************************"; 【思路】 首先两字符串中的元素个数要相同,将两串字符分别存放在数组中,那么字符串中…...
前端如何安全存储密钥,防止信息泄露
场景 把公钥硬编码在前端代码文件里,被公司安全检测到了要整改,于是整理几种常见的前端密钥存储方案。 1. 设置环境变量再读取 在打包或部署前端应用时,可以将密钥配置为环境变量,在应用运行时通过环境变量读取密钥。这样可以将密…...
银行电子户分账解决电商行业哪些问题
随着电子商务的快速发展,电商银行电子户分账作为金融科技领域的重要一环,逐渐成为现代金融业务的核心。本文将详细探讨电商银行电子户分账的原理、操作流程、安全措施以及在电子商务中的重要作用。 二、电商银行电子户分账的基本概念 电商银行电子户分…...
Web音乐库:SpringBoot实现的音乐网站
2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统,它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等,非常…...
Rust: 加密算法库 ring 如何用于 RSA 数字签名?
本来用 rsa 库基本搞定,但文心一言建议改用 ring 库。原因是 rsa 库已经放弃维护,而 ring 库性能公认很好。但是如何进行 RSA 数字签名,网上几乎查不到这方面材料。仔细查看了 ring 库的源代码和代码注释,终于完成趟坑。总结一下供…...
Matplotlib 网格线
Matplotlib 网格线 Matplotlib 是一个强大的 Python 绘图库,广泛用于数据可视化。在 Matplotlib 中,网格线是一种常用的辅助工具,用于增强图表的可读性和美观性。本文将详细介绍如何在 Matplotlib 中添加和使用网格线。 1. 简介 网格线是在…...
钉钉机器人禅道消息通知@指派人
钉钉、禅道怎么设置webhook? 点击查看:获取自定义机器人 Webhook 地址 在禅道上配置钉钉机器人webhook,使用管理员账号登录,找到通知设置 添加webhook 添加webhook所需要的数据即可 webhook设置,根据自己的实际…...
我的新书出版啦!和大家聊聊写书的酸甜苦辣
我的新书出版啦!小伙伴们问是不是赚翻了? 大家好,我是码哥。我的新书《Redis 高手心法》出版后(2024 年 8 月份出版),有一些小伙伴问了我一些问题: 写书是不是赚了很多钱?我也想写…...
【福建医科大学附属第一医院-注册安全分析报告】
前言 由于网站注册入口容易被黑客攻击,存在如下安全问题: 暴力破解密码,造成用户信息泄露短信盗刷的安全问题,影响业务及导致用户投诉带来经济损失,尤其是后付费客户,风险巨大,造成亏损无底洞 …...
第二届新生程序设计竞赛热身赛(C语言)
A:饥饿的XP XP迷失在X星球,他醒来时已经很久很久很久没有吃过东西了。他突然发现身边有一张地图,上面有X星球上每一个食物供给点的位置。太好了,XP跳了起来。他决定先把肚子填饱再去寻找其他伙伴。现在已知XP的位置(X, Y),以及他的…...
WebSocket和HTTP请求的区别
1. 连接方式 HTTP请求:基于“请求-响应”模式。每次通信都要重新建立连接,客户端发送请求后服务器返回响应,连接就断开了。这种模式通常适合不频繁更新的数据,如静态页面的加载。WebSocket:支持长连接,连接…...
【Python · Pytorch】人工神经网络 ANN(中)
【Python Pytorch】人工神经网络 ANN(中) 6. 反向传播6.1 梯度下降法6.1.1 线搜索方法6.1.2 微分 & 导数6.1.3 偏导数6.1.4 Jacobian矩阵6.1.5 梯度 & 梯度下降法按维度介绍 6.1.6 面临挑战平原现象 & 振荡现象局部最小值鞍点梯度消失梯度爆…...
穷举vs暴搜vs深搜vs回溯vs剪枝 算法专题
一. 全排列 全排列 class Solution {List<List<Integer>> ret;List<Integer> path;boolean[] check;public List<List<Integer>> permute(int[] nums) {ret new ArrayList<>();//存放结果path new ArrayList<>();存放每个路径的…...
Uni-App-02
条件编译 条件编译概念 不同的运行平台终归有些专有的特性,无法实现跨平台完全兼容,例如:微信小程序导航栏右上角的关闭图标。 uni-app提供了一种“条件编译”机制,可以针对特定的平台编译执行特定的代码,否则不执行。…...
在做题中学习(72):最小栈
解法:pair<int,int>解决 思路:stack里存pair,push时,first存当前值,而每次push都要更新pair的second,使它成为更小值,最后的getmin,只用取top().second即可拿到最小值。 cla…...
详解软件设计中分库分表的几种实现以及应用示例
详解软件设计中分库分表的几种实现以及应用示例https://mp.weixin.qq.com/s?__bizMzkzMTY0Mjc0Ng&mid2247485108&idx1&sn8b3b803c120c163092c70fa65fe5541e&chksmc266aaa1f51123b7af4d7a3113fe7c25daa938a04ced949fb71a8b7773e861fb93d907435386#rd...
随着飞行汽车的亮相,在环保方面有什么保护措施吗
飞行汽车具备环保潜力,采用电动或混合动力系统减少污染,并拓展应用场景。多家企业布局,沃飞长空作为国内eVTOL(电动垂直起降航空器)研发的领先企业,在环保这一点做的非常到位,AE200采用纯电动力系统,零碳排放,静默飞行…...
docker安装、设置非sudo执行、卸载
安装 sudo snap install docker 设置docker非sudo执行 sudo groupadd docker sudo usermod -aG docker $USER newgrp docker sudo chown root:docker /var/run/docker.sock 卸载docker 1.删除docker及安装时自动安装的所有包 apt-get autoremove docker docker-ce docker-…...
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数组即可。 至于每一种情况是否可以达到…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
