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

专栏导读

本专栏收录于《华为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();
        List 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 map) { int n = (int) Math.sqrt(map.size());
        // 将一维数组转换为二维矩阵
        int[][] matrix = new int[n][n];
        // 用队列存储感染区域
        Queue 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、输出

3、说明

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

🏆下一篇：华为OD机试 - 最长的顺子 - 感谢@禁止你发言提供的更简便算法（Java 2023 B卷 200分）

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷+C卷）