网站开发报价清单,网站自然排名优化,建行商城网站,seo优化实训报告目录 专栏导读一、题目描述二、输入描述三、输出描述四、解题思路五、Java算法源码六、效果展示1、输入2、输出3、说明 华为OD机试 2024C卷题库疯狂收录中#xff0c;刷题点这里 专栏导读
本专栏收录于《华为OD机试#xff08;JAVA#xff09;真题#xff08;A卷B卷C卷刷题点这里 专栏导读
本专栏收录于《华为OD机试JAVA真题A卷B卷C卷》。
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
一、题目描述
在一个地图中地图有N*N个区域组成有部分区域被感染病菌。
感染区每天都会把周围上下左右的4个区域感染。
请根据给定的地图计算多少天后全部区域都会被感染。 如果初始地图上所有区域全部都被感染或者没有被感染返回-1
二、输入描述
一行N*N个数字只包含0,1不会有其他数字表示一个地图数字间用“”分割0表示未感染区域1表示已经感染区域 每N个数字表示地图中一行输入数据共表示N行N列的区域地图。 例如输入1,0,1,0,0,0,1,0,1表示地图
1 0 1 0 0 0 1 0 1
三、输出描述
一个整数表示经过多少天后全部区域都被感染1 N 200
四、解题思路
将输入字符串转换为一维数组将一维数组转换为二维矩阵定义感染区域队列arrQueue 将一维数组转换为二维矩阵将感染区域加入队列 判断特殊情况记录未感染区域数量记录四个方向的偏移量记录感染天数当队列不为空且还有未感染区域时进行循环 取出队首元素获取队首元素的坐标记录感染天数遍历四个方向 定义新的横坐标定义新的纵坐标判断边界如果该区域未感染 未感染区域数量减一标记该区域已感染将该区域加入队列 返回感染天数 返回感染天数
五、Java算法源码
package com.guor.od;import java.util.*;public class OdTest {public static void main(String[] args) {Scanner sc new Scanner(System.in);String input sc.nextLine();ListInteger map new ArrayList();int pos 0;String token ;// 将输入字符串转换为一维数组while ((pos input.indexOf(,)) ! -1) {token input.substring(0, pos);map.add(Integer.parseInt(token));input input.substring(pos 1);}map.add(Integer.parseInt(input));// 输出感染天数System.out.println(getResult(map));}public static int getResult(ListInteger map) {int n (int) Math.sqrt(map.size());// 将一维数组转换为二维矩阵int[][] matrix new int[n][n];// 用队列存储感染区域Queueint[] arrQueue new LinkedList();for (int i 0; i n; i) {for (int j 0; j n; j) {// 将一维数组转换为二维矩阵matrix[i][j] map.get(i * n j);// 将感染区域加入队列if (matrix[i][j] 1) {arrQueue.offer(new int[]{i, j});}}}// 判断特殊情况if (arrQueue.isEmpty() || arrQueue.size() map.size()) {return -1;}// 记录未感染区域数量int healthyNum map.size() - arrQueue.size();// 记录四个方向的偏移量int[][] offSets {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 记录感染天数int day 0;// 当队列不为空且还有未感染区域时进行循环while (!arrQueue.isEmpty() healthyNum 0) {// 取出队首元素int[] arr arrQueue.poll();// 获取队首元素的坐标int x arr[0];int y arr[1];// 记录感染天数day matrix[x][y] 1;// 遍历四个方向for (int[] offset : offSets) {// 新的横坐标int x_new x offset[0];// 新的纵坐标int y_new y offset[1];// 判断边界if (x_new 0 || x_new n || y_new 0 || y_new n) {continue;}// 如果该区域未感染if (matrix[x_new][y_new] 0) {// 未感染区域数量减一healthyNum--;// 标记该区域已感染matrix[x_new][y_new] day;// 将该区域加入队列arrQueue.offer(new int[]{x_new, y_new});}}}return day - 1; // 返回感染天数}
}六、效果展示
1、输入
1,0,1,0,0,0,1,0,1
2、输出
2
3、说明
一天以后地图中仅剩余中心点未被感染2天后全部被感染。 下一篇华为OD机试 - 最长的顺子 - 感谢禁止你发言提供的更简便算法Java 2023 B卷 200分
本文收录于华为OD机试JAVA真题A卷B卷C卷
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
