华为OD机试E卷 -计算疫情扩散时间（Java & Python& JS & C++ & C ）

https://blog.csdn.net/banxia_frontend/article/details/141439262

最新华为OD机试

真题目录：点击查看目录 华为OD面试真题精选：点击立即查看

题目描述

在一个地图中(地图由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

输入

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

输出

2

说明

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

示例2

输入

1,1,1,1,1,1,1,1,1

输出

-1

说明

全部都感染

解题思路

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.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(getInfectionDays(map)); // 输出感染天数
    }

    public static int getInfectionDays(List<Integer> map) {
        int n = (int) Math.sqrt(map.size());

        int[][] matrix = new int[n][n]; // 将一维数组转换为二维矩阵

        Queue<int[]> q = new LinkedList<>(); // 用队列存储感染区域

        int healthy = 0; // 记录未感染区域数量

        int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 记录四个方向的偏移量

        for (int i = 0; i < n * n; i++) {
            int x = i / n;
            int y = i % n;
            matrix[x][y] = map.get(i); // 将一维数组转换为二维矩阵
            if (matrix[x][y] == 1) {
                q.offer(new int[]{x, y}); // 将感染区域加入队列
            } else {
                healthy++; // 计算未感染区域数量
            }
        }

        if (healthy == 0 || healthy == n * n) { // 判断特殊情况
            return -1;
        }

        int day = 0; // 记录感染天数
        while (!q.isEmpty() && healthy > 0) { // 当队列不为空且还有未感染区域时，进行循环
            int[] tmp = q.poll(); // 取出队首元素
            int x = tmp[0], y = tmp[1]; // 获取队首元素的坐标
            day = matrix[x][y] + 1; // 记录感染天数

            for (int[] offset : offsets) { // 遍历四个方向
                int newX = x + offset[0]; // 新的横坐标
                int newY = y + offset[1]; // 新的纵坐标

                if (newX >= 0 && newX < n && newY >= 0 && newY < n && matrix[newX][newY] == 0) { // 判断边界和未感染区域
                    healthy--; // 未感染区域数量减一
                    matrix[newX][newY] = day; // 标记该区域已感染
                    q.offer(new int[]{newX, newY}); // 将该区域加入队列
                }
            }
        }

        return day - 1; // 返回感染天数
    }
}

Python

import math
from queue import Queue

def getInfectionDays(map):
    # 计算地图边长，即每一行（或列）的元素个数
    n = int(math.sqrt(len(map)))
    
    # 构建二维矩阵表示地图，初始值为0
    matrix = [[0 for j in range(n)] for i in range(n)]
    
    # 初始化一个队列，用于存放已感染区域的位置
    q = Queue()
    
    # 遍历地图，将已感染区域的坐标入队，并初始化二维矩阵
    for i in range(n):
        for j in range(n):
            matrix[i][j] = map[i * n + j]
            if matrix[i][j] == 1:
                q.put((i, j))
    
    # 如果队列为空（没有感染区域）或所有区域都已被感染，返回-1
    if q.empty() or q.qsize() == len(map):
        return -1
    
    # 计算未感染区域的数量
    healthy = len(map) - q.qsize()
    
    # 定义四个方向的偏移量（上下左右）
    offsets = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    
    # 初始化天数计数器
    day = 0
    
    # 广度优先搜索，通过队列逐层扩散感染
    while not q.empty() and healthy > 0:
        tmp = q.get()
        x, y = tmp[0], tmp[1]
        day = matrix[x][y] + 1  # 更新天数
        
        # 对当前节点的四个方向进行探索
        for offset in offsets:
            new_x = x + offset[0]
            new_y = y + offset[1]
            
            # 检查新坐标是否越界
            if new_x < 0 or new_x >= n or new_y < 0 or new_y >= n:
                continue
            
            # 如果新坐标的区域未被感染，则将其感染，并将其加入队列
            if matrix[new_x][new_y] == 0:
                healthy -= 1
                matrix[new_x][new_y] = day
                q.put((new_x, new_y))
    
    # 返回全部区域被感染所需的天数，由于最后一天的增加已在循环中完成，故减1
    return day - 1

# 读取输入，并转换成整数列表
input_str = input()
input_list = list(map(int, input_str.split(",")))

# 输出计算结果
print(getInfectionDays(input_list))

JavaScript

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

function getInfectionDays(map) {
  const n = Math.sqrt(map.length);

  const matrix = new Array(n).fill().map(() => new Array(n)); // 将一维数组转换为二维矩阵

  const q = []; // 用队列存储感染区域

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      matrix[i][j] = map[i * n + j]; // 将一维数组转换为二维矩阵
      if (matrix[i][j] === 1) q.push([i, j]); // 将感染区域加入队列
    }
  }

  if (q.length === 0 || q.length === map.length) { // 判断特殊情况
    return -1;
  }

  let healthy = map.length - q.length; // 记录未感染区域数量

  const offsets = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // 记录四个方向的偏移量

  let day = 0; // 记录感染天数
  while (q.length > 0 && healthy > 0) { // 当队列不为空且还有未感染区域时，进行循环
    const [x, y] = q.shift(); // 取出队首元素
    day = matrix[x][y] + 1; // 记录感染天数

    for (const offset of offsets) { // 遍历四个方向
      const [dx, dy] = offset;
      const newX = x + dx; // 新的横坐标
      const newY = y + dy; // 新的纵坐标

      if (newX < 0 || newX >= n || newY < 0 || newY >= n) continue; // 判断边界

      if (matrix[newX][newY] === 0) { // 如果该区域未感染
        healthy--; // 未感染区域数量减一
        matrix[newX][newY] = day; // 标记该区域已感染
        q.push([newX, newY]); // 将该区域加入队列
      }
    }
  }

  return day - 1; // 返回感染天数
}

rl.on('line', (input) => {
  const map = input.split(',').map(Number);
  console.log(getInfectionDays(map));
});

C++

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

int getInfectionDays(vector<int>& map) {
    int n = sqrt(map.size());

    vector<vector<int>> matrix(n, vector<int>(n)); // 将一维数组转换为二维矩阵

    queue<pair<int, int>> q; // 用队列存储感染区域

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i][j] = map[i * n + j]; // 将一维数组转换为二维矩阵
            if (matrix[i][j] == 1) q.push({i, j}); // 将感染区域加入队列
        }
    }

    if (q.empty() || q.size() == map.size()) { // 判断特殊情况
        return -1;
    }

    int healthy = map.size() - q.size(); // 记录未感染区域数量

    vector<vector<int>> offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 记录四个方向的偏移量

    int day = 0; // 记录感染天数
    while (!q.empty() && healthy > 0) { // 当队列不为空且还有未感染区域时，进行循环
        pair<int, int> tmp = q.front(); // 取出队首元素
        q.pop(); // 弹出队首元素
        int x = tmp.first, y = tmp.second; // 获取队首元素的坐标
        day = matrix[x][y] + 1; // 记录感染天数

        for (vector<int>& offset : offsets) { // 遍历四个方向
            int newX = x + offset[0]; // 新的横坐标
            int newY = y + offset[1]; // 新的纵坐标

            if (newX < 0 || newX >= n || newY < 0 || newY >= n) continue; // 判断边界

            if (matrix[newX][newY] == 0) { // 如果该区域未感染
                healthy--; // 未感染区域数量减一
                matrix[newX][newY] = day; // 标记该区域已感染
                q.push({newX, newY}); // 将该区域加入队列
            }
        }
    }

    return day - 1; // 返回感染天数
}

int main() {
    string input;
    getline(cin, input);
    vector<int> map;
    size_t pos = 0;
    string token;
    while ((pos = input.find(",")) != string::npos) { // 将输入字符串转换为一维数组
        token = input.substr(0, pos);
        map.push_back(stoi(token));
        input.erase(0, pos + 1);
    }
    map.push_back(stoi(input));
    cout << getInfectionDays(map) << endl; // 输出感染天数
    return 0;
}

C语言

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
typedef struct {
    int x, y;
} Point;

typedef struct {
    Point *elements;
    int size;
    int front;
    int rear;
    int capacity;
} Queue;

Queue* createQueue(int capacity) {
    Queue *queue = (Queue *)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->elements = (Point *)malloc(queue->capacity * sizeof(Point));
    return queue;
}

int isFull(Queue* queue) {
    return (queue->size == queue->capacity);
}

int isEmpty(Queue* queue) {
    return (queue->size == 0);
}

void enqueue(Queue* queue, Point item) {
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->elements[queue->rear] = item;
    queue->size = queue->size + 1;
}

Point dequeue(Queue* queue) {
    if (isEmpty(queue))
        return (Point){-1, -1};
    Point item = queue->elements[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}

int getInfectionDays(int *map, int size) {
    int n = sqrt(size);
    int *matrix = (int *)malloc(size * sizeof(int));
    Queue *q = createQueue(size);
    Point p;
    int i, j, k, healthy = 0, day = 0;

    // Initialize matrix and queue with infected areas
    for (i = 0; i < size; i++) {
        matrix[i] = map[i];
        if (matrix[i] == 1) {
            p.x = i / n;
            p.y = i % n;
            enqueue(q, p);
        } else {
            healthy++;
        }
    }

    if (isEmpty(q) || healthy == 0) {
        free(matrix);
        free(q->elements);
        free(q);
        return -1;
    }

    int offsets[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    while (!isEmpty(q) && healthy > 0) {
        int level_size = q->size;
        for (k = 0; k < level_size; k++) {
            p = dequeue(q);
            for (i = 0; i < 4; i++) {
                int newX = p.x + offsets[i][0];
                int newY = p.y + offsets[i][1];
                if (newX >= 0 && newX < n && newY >= 0 && newY < n && matrix[newX * n + newY] == 0) {
                    matrix[newX * n + newY] = 1;
                    healthy--;
                    enqueue(q, (Point){newX, newY});
                }
            }
        }
        day++;
    }

    free(matrix);
    free(q->elements);
    free(q);

    return day;
}

int main() {
    char input[1024];
    fgets(input, sizeof(input), stdin);

    int *map = malloc(40000 * sizeof(int));  
    int size = 0, num;
    char *token = strtok(input, ",");

    while (token != NULL) {
        sscanf(token, "%d", &num);
        map[size++] = num;
        token = strtok(NULL, ",");
    }

    int result = getInfectionDays(map, size);
    printf("%d\n", result);
    free(map);

    return 0;
}

完整用例

用例1

1

用例2

0

用例3

1,0,0,0

用例4

0,0,0,0,0,0,0,0,0

用例5

1,1,1,1,1,1,1,1,1

用例6

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

用例7

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

用例8

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

用例9

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

用例10

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