题面描述

在一个地图中（地图由 $n \times n$ 个区域组成），有部分区域被感染病菌。感染区域每天都会将周围（上下左右）的 4 个区域感染。请根据给定的地图计算，多少天以后，全部区域都会被感染。如果初始地图上所有区域全部都被感染，或者没有被感染区域，返回 $-1$。

思路

按照天数进行分层$bfs$,首先，将输入的地图数据解析为二维数组，并检查初始状态是否所有区域已感染或无感染区域，若满足则直接返回 -1。接着，将所有初始被感染的区域加入队列，作为BFS的起点。然后，按天数逐层遍历队列中的感染区域，每天向上下左右四个方向扩散感染未被感染的区域，并将新感染的区域加入队列。记录经过的天数，直到所有区域都被感染为止。如果在扩散结束后仍有未被感染的区域，说明无法完全感染，返回 -1；否则，返回所需的天数。

具体步骤如下：

1. 地图解析：首先将输入的字符串解析成一个二维数组表示的地图。

2. 初始化：

   • 检查初始地图是否所有区域都已被感染或没有任何被感染的区域，如果是，直接返回 $-1$。
   • 将所有初始被感染的区域加入队列，并记录它们的位置。

3. 广度优先搜索：

   • 每天为一次循环，从队列中取出当前所有感染区域，向四个方向扩散感染未被感染的区域，并将新感染的区域加入队列。
   • 记录经过的天数。

4. 终止条件：

   • 当队列为空时，检查是否所有区域都已被感染。如果是，返回天数；否则，返回 $-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

说明

全部都感染