华为OD机试 - 疫情扩散时间计算 - 矩阵（Java 2024 C卷 200分）

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为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

四、解题思路

1. 将输入字符串转换为一维数组；
2. 将一维数组转换为二维矩阵；
3. 定义感染区域队列arrQueue；
   • 将一维数组转换为二维矩阵；
   • 将感染区域加入队列；
4. 判断特殊情况；
5. 记录未感染区域数量；
6. 记录四个方向的偏移量；
7. 记录感染天数；
8. 当队列不为空且还有未感染区域时，进行循环；
   • 取出队首元素；
   • 获取队首元素的坐标；
   • 记录感染天数；
   • 遍历四个方向；
     • 定义新的横坐标；
     • 定义新的纵坐标；
     • 判断边界；
     • 如果该区域未感染；
       • 未感染区域数量减一；
       • 标记该区域已感染；
       • 将该区域加入队列；
   • 返回感染天数；
9. 返回感染天数；

五、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();
        List<Integer> 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(List<Integer> map) {
        int n = (int) Math.sqrt(map.size());
        // 将一维数组转换为二维矩阵
        int[][] matrix = new int[n][n];
        // 用队列存储感染区域
        Queue<int[]> 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

六、效果展示

1、输入

1,0,1,0,0,0,1,0,1

2、输出

2

3、说明

一天以后，地图中仅剩余中心点未被感染，2天后，全部被感染。