华为OD机试真题---矩阵扩散
一、题目描述
存在一个m*n的二维数组，其成员取值范围为0，1。其中值为1的元素具备扩散性，每经过1S，将上下左右值为0的元素同化为1。将数组所有成员初始化为0，将矩阵的[i, j]和[m,n]位置上元素修改成1后，在经过多长时间所有元素变为1。
二、输入描述
输出数据中的前2个数字表示这是一个m*n的矩阵，m和n不会超过1024大小;中间两个数字表示一个初始扩散点位置;最后2个数字表示另一个扩散点位置。
三、输出描述
输出矩阵的所有元素变为1所需要秒数。
用例
输入
4,4,0,0,3,3
输出
3
说明
输入数据中的前2个数字表示这是一个4*4的矩阵；
中间两个数字表示一个初始扩散点位置为0,0；
最后2个数字表示另一个扩散点位置为3,3。
给出的样例是一个简单模型，初始点在对角线上，达到中间的位置分别为3次迭代，即3秒。所以输出为3。
四、代码实现
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)。
- 初始化矩阵
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)
初始化后的矩阵如下：
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1
- 调用 minTimeToDiffuse 函数
System.out.println(minTimeToDiffuse(matrix, i, j, k, l));
- minTimeToDiffuse 函数内部执行过程
- 初始状态
- 队列中包含两个位置：(0,0) 和 (3,3)
- 时间 time 初始化为 0
- 第1轮扩散
- 处理 (0,0)：
- 向上、左无效，向右、下扩散到 (0,1) 和 (1,0)
- 处理 (3,3)：
- 向下、右无效，向左、上扩散到 (3,2) 和 (2,3)
- 处理 (0,0)：
- 更新后的矩阵：
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)
更新后的矩阵：
- 向下、右无效，向左、上扩散到 (2,2) 和 (1,3)
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)
更新后的矩阵：
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)
更新后的矩阵：
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
- 队列中没有新增位置
- 时间 time 保持为 3
- 输出结果
最终输出的时间为 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所需的最短时间。
解题思路与算法实现
-
初始化矩阵：
- 创建一个m行n列的二维数组
matrix，所有元素初始化为0。 - 将两个指定位置
(i, j)和(k, l)的元素设置为1。
- 创建一个m行n列的二维数组
-
广度优先搜索（BFS）：
- 使用队列
queue来进行广度优先搜索。 - 初始时，将两个扩散点的位置
(i, j)和(k, l)加入队列。 - 使用一个变量
time来记录扩散的时间。 - 在每一轮扩散中，遍历队列中的所有位置，并尝试向上下左右四个方向扩散。
- 如果新的位置在矩阵范围内且值为0，则将其设置为1，并加入队列中等待下一轮扩散。
- 如果当前轮次有位置发生变化，则
time增加1。 - 当队列为空时，表示没有更多的位置可以扩散，算法结束。
- 使用队列
-
判断扩散是否完成：
- 由于题目要求矩阵中的所有元素都变为1，因此在每一轮扩散后，可以检查矩阵中是否还有0元素。
- 如果矩阵中已经没有0元素，则可以提前结束算法，并返回当前的
time值。 - 然而，在本题的特定情况下，由于是从两个点开始同时扩散，且矩阵是连通的（即没有障碍物），因此最终矩阵中的所有元素一定会变为1。因此，这一步判断可以省略，直接通过队列为空来判断算法是否结束即可。
-
优化与注意事项：
- 由于矩阵的大小可能达到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秒。
通过以上详细解析与扩展描述，我们可以更深入地理解题目的要求、解题思路、算法实现以及代码中的关键细节。