#P3240. 计算疫情扩散时间(200分)
-
1000ms
Tried: 57
Accepted: 25
Difficulty: 6
所属公司 :
华为od
计算疫情扩散时间(200分)
题面描述
在一个地图中(地图由 n×n 个区域组成),有部分区域被感染病菌。感染区域每天都会将周围(上下左右)的 4 个区域感染。请根据给定的地图计算,多少天以后,全部区域都会被感染。如果初始地图上所有区域全部都被感染,或者没有被感染区域,返回 −1。
思路
按照天数进行分层bfs,首先,将输入的地图数据解析为二维数组,并检查初始状态是否所有区域已感染或无感染区域,若满足则直接返回 -1。接着,将所有初始被感染的区域加入队列,作为BFS的起点。然后,按天数逐层遍历队列中的感染区域,每天向上下左右四个方向扩散感染未被感染的区域,并将新感染的区域加入队列。记录经过的天数,直到所有区域都被感染为止。如果在扩散结束后仍有未被感染的区域,说明无法完全感染,返回 -1;否则,返回所需的天数。
具体步骤如下:
-
地图解析:首先将输入的字符串解析成一个二维数组表示的地图。
-
初始化:
- 检查初始地图是否所有区域都已被感染或没有任何被感染的区域,如果是,直接返回 −1。
- 将所有初始被感染的区域加入队列,并记录它们的位置。
-
广度优先搜索:
- 每天为一次循环,从队列中取出当前所有感染区域,向四个方向扩散感染未被感染的区域,并将新感染的区域加入队列。
- 记录经过的天数。
-
终止条件:
- 当队列为空时,检查是否所有区域都已被感染。如果是,返回天数;否则,返回 −1(意味着存在无法被感染的区域)。
代码分析
-
输入处理:将输入的字符串按逗号分割,并转换成整数填充到二维数组
grid中。同时记录地图的大小 N。 -
边界情况处理:
- 如果所有区域已被感染,或没有任何被感染的区域,返回 −1。
-
BFS 实现:
- 使用队列
q存储当前被感染的区域。 - 使用二维数组
directions表示四个可能的移动方向。 - 记录已经被感染的区域数
infected_count,初始化为初始被感染区域的数量。 - 每次循环代表一天,遍历当前队列中的所有区域,尝试向四个方向扩散感染。
- 如果成功感染一个新的区域,更新
infected_count并将其加入队列。 - 循环直到队列为空。
- 使用队列
-
结果判断:
- 如果
infected_count等于总区域数,返回天数;否则,返回 −1。
- 如果
cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
string input;
getline(cin, input);
// 分割输入
vector<int> nums;
string num = "";
for(char c: input){
if(c == ','){
if(!num.empty()){
nums.push_back(stoi(num));
num = "";
}
}
else{
num += c;
}
}
if(!num.empty()){
nums.push_back(stoi(num));
}
// 确定N
int total = nums.size();
int N = sqrt(total);
if(N*N != total){
// 如果不能构成正方形地图,输出-1
cout << -1;
return 0;
}
// 构建地图
vector<vector<int>> grid(N, vector<int>(N, 0));
int index = 0;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
grid[i][j] = nums[index++];
}
}
// 检查全是1或全是0
int ones = 0, zeros = 0;
for(auto &row: grid){
for(auto &cell: row){
if(cell ==1) ones++;
else zeros++;
}
}
if(zeros ==0 || ones ==0){
cout << -1;
return 0;
}
// BFS初始化
queue<pair<int,int>> q;
// 记录被感染的数量
int infected_count = ones;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(grid[i][j] ==1){
q.push({i,j});
}
}
}
// 四个方向
vector<pair<int,int>> directions = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int days = -1;
while(!q.empty()){
int size = q.size();
days++;
for(int i=0;i<size;i++){
auto [x, y] = q.front(); q.pop();
for(auto &[dx, dy]: directions){
int nx = x + dx, ny = y + dy;
if(nx >=0 && nx <N && ny >=0 && ny <N && grid[nx][ny]==0){
grid[nx][ny] =1;
infected_count++;
q.push({nx, ny});
}
}
}
}
// 检查是否全部被感染
if(infected_count == N*N){
cout << days;
}
else{
cout << -1;
}
}
python
import math
from collections import deque
def main():
input_str = input().strip()
# 分割输入
nums = list(map(int, input_str.split(',')))
# 确定N
total = len(nums)
N = int(math.sqrt(total))
if N * N != total:
# 如果不能构成正方形地图,输出-1
print(-1)
return
# 构建地图
grid = []
index = 0
for i in range(N):
row = []
for j in range(N):
row.append(nums[index])
index += 1
grid.append(row)
# 检查全是1或全是0
ones = sum(cell == 1 for row in grid for cell in row)
zeros = total - ones
if zeros == 0 or ones == 0:
print(-1)
return
# BFS初始化
q = deque()
infected_count = ones
for i in range(N):
for j in range(N):
if grid[i][j] == 1:
q.append((i, j))
# 四个方向
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
days = -1
while q:
size = len(q)
days += 1
for _ in range(size):
x, y = q.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < N and 0 <= ny < N and grid[nx][ny] == 0:
grid[nx][ny] = 1
infected_count += 1
q.append((nx, ny))
# 检查是否全部被感染
if infected_count == N * N:
print(days)
else:
print(-1)
if __name__ == "__main__":
main()
java
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
// 读取输入
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine().trim();
// 分割输入
String[] tokens = input.split(",");
List<Integer> nums = new ArrayList<>();
for(String token : tokens){
nums.add(Integer.parseInt(token));
}
// 确定N
int total = nums.size();
int N = (int)Math.sqrt(total);
if(N * N != total){
// 如果不能构成正方形地图,输出-1
System.out.println(-1);
return;
}
// 构建地图
int[][] grid = new int[N][N];
int index = 0;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
grid[i][j] = nums.get(index++);
}
}
// 检查全是1或全是0
int ones = 0, zeros = 0;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(grid[i][j] == 1) ones++;
else zeros++;
}
}
if(zeros == 0 || ones == 0){
System.out.println(-1);
return;
}
// BFS初始化
Queue<int[]> queue = new LinkedList<>();
int infected_count = ones;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
if(grid[i][j] == 1){
queue.offer(new int[]{i, j});
}
}
}
// 四个方向
int[][] directions = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int days = -1;
while(!queue.isEmpty()){
int size = queue.size();
days++;
for(int i=0; i<size; i++){
int[] current = queue.poll();
int x = current[0];
int y = current[1];
for(int[] dir : directions){
int nx = x + dir[0];
int ny = y + dir[1];
if(nx >=0 && nx < N && ny >=0 && ny < N && grid[nx][ny] == 0){
grid[nx][ny] = 1;
infected_count++;
queue.offer(new int[]{nx, ny});
}
}
}
}
// 检查是否全部被感染
if(infected_count == N * N){
System.out.println(days);
}
else{
System.out.println(-1);
}
}
}
题目内容
在一个地图中(地图由 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
输入
0,0,0,0
输出
-1
说明
无感染区域
样例3
输入
1,1,1,1,1,1,1,1,1
输出
-1
说明
全部都感染