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

计算疫情扩散时间

该专栏题目包含两部分:
100 分值部分题目
200 分值部分题目
所有题目都会陆续更新,订阅防丢失

题目描述

在一个地图中(地图由 N ∗ N N*N NN 个区域组成),有部分区域被感染病菌。

感染区域每天都会把周围(上下左右)的4个区域感染。

请根据给定的地图计算,多少天以后,全部区域都会被感染。

如果初始地图上所有区域全部都被感染,或者没有被感染区域,返回-1

输入描述

  • N ∗ N N*N NN 个数字(只包含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 1N<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;}}}

相关文章:

计算疫情扩散时间

该专栏题目包含两部分&#xff1a; 100 分值部分题目 200 分值部分题目 所有题目都会陆续更新&#xff0c;订阅防丢失 题目描述 在一个地图中(地图由 N ∗ N N*N N∗N 个区域组成)&#xff0c;有部分区域被感染病菌。 感染区域每天都会把周围(上下左右)的4个区域感染。 请…...

【Windows11】24H2 内存占用高(截至10月31日)

文章目录 一、问题二、解决三、原因 一、问题 系统版本&#xff1a; 内存只有32GB。 以前只有我在运行数据处理程序的时候内存占用才会很高&#xff0c;日常情况下应该只有40%、50%左右的。 但是24H2&#xff0c;日常情况下内存占用80%以上。 而我只开了很少的应用&#…...

题目:多个字符从两端移动,向中间汇聚

【多个字符从两端移动&#xff0c;向中间汇聚】 char arr1[] "Good Good Study,Day Day Up!" ; char arr2[] "***************************"; 【思路】 首先两字符串中的元素个数要相同&#xff0c;将两串字符分别存放在数组中&#xff0c;那么字符串中…...

前端如何安全存储密钥,防止信息泄露

场景 把公钥硬编码在前端代码文件里&#xff0c;被公司安全检测到了要整改&#xff0c;于是整理几种常见的前端密钥存储方案。 1. 设置环境变量再读取 在打包或部署前端应用时&#xff0c;可以将密钥配置为环境变量&#xff0c;在应用运行时通过环境变量读取密钥。这样可以将密…...

银行电子户分账解决电商行业哪些问题

随着电子商务的快速发展&#xff0c;电商银行电子户分账作为金融科技领域的重要一环&#xff0c;逐渐成为现代金融业务的核心。本文将详细探讨电商银行电子户分账的原理、操作流程、安全措施以及在电子商务中的重要作用。 二、电商银行电子户分账的基本概念 电商银行电子户分…...

Web音乐库:SpringBoot实现的音乐网站

2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统&#xff0c;它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等&#xff0c;非常…...

Rust: 加密算法库 ring 如何用于 RSA 数字签名?

本来用 rsa 库基本搞定&#xff0c;但文心一言建议改用 ring 库。原因是 rsa 库已经放弃维护&#xff0c;而 ring 库性能公认很好。但是如何进行 RSA 数字签名&#xff0c;网上几乎查不到这方面材料。仔细查看了 ring 库的源代码和代码注释&#xff0c;终于完成趟坑。总结一下供…...

Matplotlib 网格线

Matplotlib 网格线 Matplotlib 是一个强大的 Python 绘图库&#xff0c;广泛用于数据可视化。在 Matplotlib 中&#xff0c;网格线是一种常用的辅助工具&#xff0c;用于增强图表的可读性和美观性。本文将详细介绍如何在 Matplotlib 中添加和使用网格线。 1. 简介 网格线是在…...

钉钉机器人禅道消息通知@指派人

钉钉、禅道怎么设置webhook&#xff1f; 点击查看&#xff1a;获取自定义机器人 Webhook 地址 在禅道上配置钉钉机器人webhook&#xff0c;使用管理员账号登录&#xff0c;找到通知设置 添加webhook 添加webhook所需要的数据即可 webhook设置&#xff0c;根据自己的实际…...

我的新书出版啦!和大家聊聊写书的酸甜苦辣

我的新书出版啦&#xff01;小伙伴们问是不是赚翻了&#xff1f; 大家好&#xff0c;我是码哥。我的新书《Redis 高手心法》出版后&#xff08;2024 年 8 月份出版&#xff09;&#xff0c;有一些小伙伴问了我一些问题&#xff1a; 写书是不是赚了很多钱&#xff1f;我也想写…...

【福建医科大学附属第一医院-注册安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞 …...

第二届新生程序设计竞赛热身赛(C语言)

A:饥饿的XP XP迷失在X星球&#xff0c;他醒来时已经很久很久很久没有吃过东西了。他突然发现身边有一张地图&#xff0c;上面有X星球上每一个食物供给点的位置。太好了&#xff0c;XP跳了起来。他决定先把肚子填饱再去寻找其他伙伴。现在已知XP的位置(X, Y)&#xff0c;以及他的…...

WebSocket和HTTP请求的区别

1. 连接方式 HTTP请求&#xff1a;基于“请求-响应”模式。每次通信都要重新建立连接&#xff0c;客户端发送请求后服务器返回响应&#xff0c;连接就断开了。这种模式通常适合不频繁更新的数据&#xff0c;如静态页面的加载。WebSocket&#xff1a;支持长连接&#xff0c;连接…...

【Python · Pytorch】人工神经网络 ANN(中)

【Python Pytorch】人工神经网络 ANN&#xff08;中&#xff09; 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

条件编译 条件编译概念 不同的运行平台终归有些专有的特性&#xff0c;无法实现跨平台完全兼容&#xff0c;例如&#xff1a;微信小程序导航栏右上角的关闭图标。 uni-app提供了一种“条件编译”机制&#xff0c;可以针对特定的平台编译执行特定的代码&#xff0c;否则不执行。…...

在做题中学习(72):最小栈

解法&#xff1a;pair<int,int>解决 思路&#xff1a;stack里存pair&#xff0c;push时&#xff0c;first存当前值&#xff0c;而每次push都要更新pair的second&#xff0c;使它成为更小值&#xff0c;最后的getmin&#xff0c;只用取top().second即可拿到最小值。 cla…...

详解软件设计中分库分表的几种实现以及应用示例

详解软件设计中分库分表的几种实现以及应用示例https://mp.weixin.qq.com/s?__bizMzkzMTY0Mjc0Ng&mid2247485108&idx1&sn8b3b803c120c163092c70fa65fe5541e&chksmc266aaa1f51123b7af4d7a3113fe7c25daa938a04ced949fb71a8b7773e861fb93d907435386#rd...

随着飞行汽车的亮相,在环保方面有什么保护措施吗

飞行汽车具备环保潜力&#xff0c;采用电动或混合动力系统减少污染&#xff0c;并拓展应用场景。多家企业布局&#xff0c;沃飞长空作为国内eVTOL(电动垂直起降航空器)研发的领先企业&#xff0c;在环保这一点做的非常到位&#xff0c;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-…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...