华为OD机试真题---矩阵扩散

ops/2024/10/21 18:38:35/

一、题目描述

存在一个m*n的二维数组，其成员取值范围为0，1。其中值为1的元素具备扩散性，每经过1S，将上下左右值为0的元素同化为1。将数组所有成员初始化为0，将矩阵的[i, j]和[m,n]位置上元素修改成1后，在经过多长时间所有元素变为1。

二、输入描述

输出数据中的前2个数字表示这是一个m*n的矩阵，m和n不会超过1024大小;中间两个数字表示一个初始扩散点位置;最后2个数字表示另一个扩散点位置。

三、输出描述

输出矩阵的所有元素变为1所需要秒数。

用例
输入
java">4,4,0,0,3,3
输出
java">3
说明

输入数据中的前2个数字表示这是一个4*4的矩阵；
中间两个数字表示一个初始扩散点位置为0,0；
最后2个数字表示另一个扩散点位置为3,3。
给出的样例是一个简单模型，初始点在对角线上，达到中间的位置分别为3次迭代，即3秒。所以输出为3。

四、代码实现

java">import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Diffusion {/*** 主函数入口* 本程序用于计算两个指定位置在二维矩阵中扩散至相同时所需最小时间* 通过命令行接收输入参数，格式为"m,n,i,j,k,l"，其中m和n分别为矩阵的行数和列数，* i、j和k、l分别为两个位置的行和列索引* * @param args 命令行参数，包含矩阵的维度和两个位置的坐标*/public static void main(String[] args) {// 创建Scanner对象以读取命令行输入Scanner scanner = new Scanner(System.in);// 读取用户输入的字符串String input = scanner.nextLine();// 使用逗号分割输入字符串，得到各个参数String[] parts = input.split(",");// 将字符串参数转换为整数，分别代表矩阵的行数、列数和两个位置的坐标int m = Integer.parseInt(parts[0]);int n = Integer.parseInt(parts[1]);int i = Integer.parseInt(parts[2]);int j = Integer.parseInt(parts[3]);int k = Integer.parseInt(parts[4]);int l = Integer.parseInt(parts[5]);// 初始化一个m*n的二维矩阵int[][] matrix = new int[m][n];// 将两个指定位置的值设为1，表示这些位置已经开始扩散matrix[i][j] = 1;matrix[k][l] = 1;// 调用minTimeToDiffuse函数，计算并打印两个位置扩散至相同时所需最小时间System.out.println(minTimeToDiffuse(matrix, i, j, k, l));}/*** 计算在二维矩阵中，从一个位置到另一个位置扩散的最短时间* 矩阵中，0 表示可扩散的位置，1 表示已扩散的位置* * @param matrix 二维矩阵，表示扩散环境* @param i 第一个位置的行坐标* @param j 第一个位置的列坐标* @param k 第二个位置的行坐标* @param l 第二个位置的列坐标* @return 返回从第一个位置到第二个位置扩散的最短时间*/private static int minTimeToDiffuse(int[][] matrix, int i, int j, int k, int l) {// 矩阵的行数int m = matrix.length;// 矩阵的列数int n = matrix[0].length;// 方向数组，表示上下左右四个方向int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 初始化队列Queue<int[]> queue = new LinkedList<>();// 将两个位置都加入队列queue.offer(new int[]{i, j});queue.offer(new int[]{k, l});// 记录时间int time = 0;// 当队列不为空时，继续扩散while (!queue.isEmpty()) {// 当前队列中的元素个数，表示当前时间单位内需要处理的扩散点数量int size = queue.size();// 记录当前时间单位内是否有位置发生变化boolean changed = false;// 遍历当前时间单位内所有需要处理的扩散点for (int s = 0; s < size; s++) {// 取出队列中的当前位置int[] current = queue.poll();assert current != null;int x = current[0];int y = current[1];// 遍历四个方向for (int[] dir : directions) {// 计算新的位置int newX = x + dir[0];int newY = y + dir[1];// 如果新位置有效且未被扩散，则进行扩散if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] == 0) {matrix[newX][newY] = 1;queue.offer(new int[]{newX, newY});changed = true;}}}// 如果当前时间单位内有位置发生变化，则时间增加if (changed) {time++;}}// 返回扩散的最短时间return time;}
}

五、运行示例解析

假设输入为 4,4,0,0,3,3，即矩阵的大小为 4x4，两个初始扩散点分别为 (0,0) 和 (3,3)。

  1. 初始化矩阵
java">int m = 4;
int n = 4;
int i = 0;
int j = 0;
int k = 3;
int l = 3;int[][] matrix = new int[m][n];
matrix[i][j] = 1; // (0,0)
matrix[k][l] = 1; // (3,3)

初始化后的矩阵如下：

java">1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1
  1. 调用 minTimeToDiffuse 函数
java">System.out.println(minTimeToDiffuse(matrix, i, j, k, l));
  1. minTimeToDiffuse 函数内部执行过程
  • 初始状态
    • 队列中包含两个位置：(0,0) 和 (3,3)
    • 时间 time 初始化为 0
  • 第1轮扩散
    • 处理 (0,0)：
      • 向上、左无效，向右、下扩散到 (0,1) 和 (1,0)
    • 处理 (3,3)：
      • 向下、右无效，向左、上扩散到 (3,2) 和 (2,3)
  • 更新后的矩阵：
java">1 1 0 0
1 0 0 0
0 0 0 1
0 0 1 1
  • 队列中新增位置：(0,1), (1,0), (3,2), (2,3)
  • 时间 time 增加到 1

第2轮扩散

  • 处理 (0,1)：
    • 向上、左无效，向右、下扩散到 (0,2) 和 (1,1)
  • 处理 (1,0)：
    • 向上、左无效，向右、下扩散到 (1,1) 和 (2,0)
  • 处理 (3,2)：
    • 向下、右无效，向左、上扩散到 (3,1) 和 (2,2)
  • 处理 (2,3)：
    • 向下、右无效，向左、上扩散到 (2,2) 和 (1,3)
      更新后的矩阵：
java">1 1 1 0
1 1 0 0
1 0 1 1
0 1 1 1
  • 队列中新增位置：(0,2), (1,1), (2,0), (3,1), (2,2), (1,3)
  • 时间 time 增加到 2

第3轮扩散

  • 处理 (0,2)：
    • 向上、左无效，向右、下扩散到 (0,3) 和 (1,2)
  • 处理 (1,1)：
    • 已经扩散过
  • 处理 (2,0)：
    • 向上、左无效，向右、下扩散到 (2,1) 和 (3,0)
  • 处理 (3,1)：
    • 向下、右无效，向左、上扩散到 (3,0) 和 (2,1)
  • 处理 (2,2)：
    • 已经扩散过
  • 处理 (1,3)：
    • 向上、右无效，向左、下扩散到 (1,2) 和 (0,3)

更新后的矩阵：

java">1 1 1 1
1 1 1 0
1 1 1 1
1 1 1 1
  • 队列中新增位置：(0,3), (1,2), (2,1), (3,0)
  • 时间 time 增加到 3

第4轮扩散

  • 处理 (0,3)：
    • 向上、右无效，向左、下扩散到 (0,2) 和 (1,3)
  • 处理 (1,2)：
    • 已经扩散过
  • 处理 (2,1)：
    • 已经扩散过
  • 处理 (3,0)：
    • 向上、左无效，向右、下扩散到 (3,1) 和 (2,0)

更新后的矩阵：

java">1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
  • 队列中没有新增位置
  • 时间 time 保持为 3
  1. 输出结果
    最终输出的时间为 3。

六、总结

输入 4,4,0,0,3,3 的情况下，两个位置 (0,0) 和 (3,3) 完全扩散至整个矩阵所需的时间为 3。感谢你的指正，希望这次解析更加准确。

以下是AI给出的解析，可以参考看一下：

详细解析与扩展描述

题目背景与要求

本题描述了一个二维矩阵中的扩散现象。在这个矩阵中，元素只有两种状态：0表示未扩散，1表示已扩散。初始时，矩阵中的所有元素都是0，除了在两个指定的位置被设置为1。这两个1具有扩散性，每经过1秒，它们会将其上下左右相邻的0元素同化为1。题目要求计算从初始状态开始，直到矩阵中的所有元素都变为1所需的最短时间。

输入与输出
  • 输入：输入数据包含6个用逗号分隔的整数。前两个整数m和n分别表示矩阵的行数和列数（1 ≤ m, n ≤ 1024）。接下来两个整数i和j表示第一个扩散点的位置（0 ≤ i < m, 0 ≤ j < n）。最后两个整数k和l表示第二个扩散点的位置（0 ≤ k < m, 0 ≤ l < n）。
  • 输出：输出一个整数，表示矩阵中所有元素变为1所需的最短时间。
解题思路与算法实现

  1. 初始化矩阵：

    • 创建一个m行n列的二维数组matrix，所有元素初始化为0。
    • 将两个指定位置(i, j)和(k, l)的元素设置为1。

  2. 广度优先搜索（BFS）：

    • 使用队列queue来进行广度优先搜索。
    • 初始时，将两个扩散点的位置(i, j)和(k, l)加入队列。
    • 使用一个变量time来记录扩散的时间。
    • 在每一轮扩散中，遍历队列中的所有位置，并尝试向上下左右四个方向扩散。
    • 如果新的位置在矩阵范围内且值为0，则将其设置为1，并加入队列中等待下一轮扩散。
    • 如果当前轮次有位置发生变化，则time增加1。
    • 当队列为空时，表示没有更多的位置可以扩散，算法结束。

  3. 判断扩散是否完成：

    • 由于题目要求矩阵中的所有元素都变为1，因此在每一轮扩散后，可以检查矩阵中是否还有0元素。
    • 如果矩阵中已经没有0元素，则可以提前结束算法，并返回当前的time值。
    • 然而，在本题的特定情况下，由于是从两个点开始同时扩散，且矩阵是连通的（即没有障碍物），因此最终矩阵中的所有元素一定会变为1。因此，这一步判断可以省略，直接通过队列为空来判断算法是否结束即可。

  4. 优化与注意事项：

    • 由于矩阵的大小可能达到1024x1024，因此算法的效率至关重要。使用队列和广度优先搜索可以确保算法在最坏情况下的时间复杂度为O(mn)，其中m和n分别是矩阵的行数和列数。
    • 在实现过程中，需要注意数组越界的问题，以及确保在每次从队列中取出元素后都进行正确的扩散操作。
代码实现细节

以下是代码实现中的一些关键细节：

  • 使用LinkedList作为队列的实现，因为它在头部插入和删除元素的操作效率较高。
  • 使用一个二维数组visited来记录矩阵中每个位置是否已经被访问过（在本题中实际上不需要，因为元素的值会变为1来表示已访问）。然而，为了代码的通用性和可读性，可以保留这个数组的概念，只是在本题中将其替换为直接修改矩阵的值。
  • 在每一轮扩散中，使用size变量来记录当前轮次需要处理的扩散点数量，以避免在扩散过程中队列的大小发生变化导致重复处理或遗漏处理。
  • 在扩散过程中，使用assert语句来确保从队列中取出的元素不为null（这是Java中的一种调试手段，可以在开发过程中帮助发现潜在的错误）。然而，在发布的生产代码中，应该使用更健壮的错误处理机制，而不是依赖assert语句。
运行示例与结果分析

对于输入4,4,0,0,3,3，算法的执行过程如下：

  • 初始化矩阵为：
    1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1
  • 经过1秒扩散后，矩阵变为：
    1 1 0 0
1 0 0 0
0 0 0 1
0 0 1 1
  • 经过2秒扩散后，矩阵变为：
    1 1 1 0
1 1 0 0
1 0 1 1
0 1 1 1
  • 经过3秒扩散后，矩阵变为全1：
    1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
  • 因此，输出结果为3秒。

通过以上详细解析与扩展描述，我们可以更深入地理解题目的要求、解题思路、算法实现以及代码中的关键细节。


http://www.ppmy.cn/ops/127344.html

相关文章

java宠物商城源码

java宠物商城源码

题目&#xff1a;java宠物商城源码 主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Mysql|大数据|SSM|SpringBoot|Vue|Jsp|MYSQL等)、学习资料、JAVA源码、技术咨询 文末联系获取 感兴趣可以先收藏起来&#xff0c;以防走丢&#xff0c;有任何选题、文档编写、代码问题也…
阅读更多...
基于神经网络的农业病虫害损失预测

基于神经网络的农业病虫害损失预测

【摘 要】鉴于农业病虫害经济损失的预测具有较强的复杂性和非线性特性&#xff0c;设计了一种新型的GRNN预测模型&#xff0c;对农业病虫害经济损失进行预测。该模型基于人工神经网络捕捉非线性变化独特的优越性&#xff0c;在神经网络技术和江苏省气象局提供的数据的基础上&am…
阅读更多...
基于SSM机场网上订票系统的设计

基于SSM机场网上订票系统的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;机票信息管理&#xff0c;订单信息管理&#xff0c;机场广告管理&#xff0c;系统管理 前台账号功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;机票信息&#xf…
阅读更多...
麒麟操作系统swap使用率过高的排查思路

麒麟操作系统swap使用率过高的排查思路

现象：用户业务环境服务器在运行时，监控平台告警swap使用99%，在系统内查询物理内存使用39%左右，swap使用达99%。 问题排查： 1）使用命令查询使用了swap空间的进程并排序： for i in `cd /proc;ls |grep "^[0-9]" |awk
阅读更多...
redis 使用

redis 使用

打开redis 前台启动 同路径下打开redis-server 出现窗口&#xff0c;即启动成功 此时关闭窗口&#xff0c;redis关闭&#xff1b; 不管有没有使用密码&#xff0c;或者使用了什么密码&#xff0c;都能连上 如果使用下文提到的redis cli增加密码&#xff0c;就只能使用你设置的…
阅读更多...
java科学收录小说网站txt

java科学收录小说网站txt

疫情那一年&#xff0c;老爸被风控措施困在了家中&#xff0c;无所事事的他&#xff0c;在微信上的广告上&#xff0c;开始接触网络爽文小说&#xff0c;一部叫《女神的上门豪婿》&#xff0c;一部叫《都市极品神医》。 随着阅读的深入&#xff0c;老爸逐渐沉迷于追更。后来在他…
阅读更多...
闯关leetcode——145. Binary Tree Postorder Traversal

闯关leetcode——145. Binary Tree Postorder Traversal

大纲 题目地址内容 解题代码地址 题目 地址 https://leetcode.com/problems/binary-tree-postorder-traversal/description/ 内容 Given the root of a binary tree, return the postorder traversal of its nodes’ values. Example 1: Input: root [1,null,2,3] Output…
阅读更多...
context.getExternalFilesDir()与返回的路径对照 Android 存储路径

context.getExternalFilesDir()与返回的路径对照 Android 存储路径

从Android 10开始&#xff0c;对于数据访问权限要求的越来越严&#xff0c;app对于私有目录的使用越来越多&#xff0c;进而对context.getExternalFilesDir()的使用也多了&#xff0c;下面是对应传不同参获取的返回路径&#xff1a; getExternalCacheDir(); 路径为&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023