Java 实现的网格疫情扩散模拟算法

这是一个经典的网格模拟问题。给定一个 3x3 的地图，用二进制字符串表示，1 代表有疫情，0 代表没有。规则很简单：每隔一个时间步，有疫情的网格会向它上下左右四个相邻网格进行扩散。我们的目标是计算多少个时间步以后整个地图都有疫情。

解决这类传播问题的核心思路是广度优先搜索（BFS）。因为每一轮扩散都是同步发生的，BFS 天然适合按层遍历，每一层就对应一个时间步。我们不需要递归，只需要维护一个队列来存储当前所有被感染的坐标点。

在实现细节上，为了代码的可读性，我封装了一个 Point 类来处理坐标转换和边界检查。这里有个小坑要注意：二维数组转一维索引时，行和列的计算不能搞混。下面的代码中，sideLength 设为 3，index 除以 sideLength 得到行号，余数得到列号。邻居节点的判断必须严格限制在 0 到 sideLength-1 之间，防止越界。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Point {
    int x = -1;
    int y = -1;
    int sideLength;

    Point(int index, int sideLength) {
        this.sideLength = sideLength;
        // 修正逻辑：x 为行，y 为列
        this.x = index / sideLength;
        this.y = index % sideLength;
    }

    // 获取上方邻居索引
    int top() {
        return x > 0 ? (x - 1) * sideLength + y : -1;
    }

    // 获取下方邻居索引
    int bottom() {
        return x < sideLength - 1 ? (x + 1) * sideLength + y : -1;
    }

    // 获取左方邻居索引
    int left() {
        return y > 0 ? x * sideLength + y - 1 : -1;
    }

    // 获取右方邻居索引
    int right() {
        return y < sideLength - 1 ? x * sideLength + y + 1 : -1;
    }
}

public class EpidemicSpread {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String mapStr = scanner.next();
        int sideLength = 3;
        int totalCells = sideLength * sideLength;
        boolean[] infected = new boolean[totalCells];
        Queue<Integer> queue = new LinkedList<>();

        // 初始化初始感染状态
        for (int i = 0; i < totalCells; i++) {
            if (mapStr.charAt(i) == '1') {
                infected[i] = true;
                queue.offer(i);
            }
        }

        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            boolean spreadHappened = false;
            
            // 处理当前时间步的所有感染源
            for (int i = 0; i < size; i++) {
                int currentIdx = queue.poll();
                Point p = new Point(currentIdx, sideLength);
                
                int[] neighbors = {p.top(), p.bottom(), p.left(), p.right()};
                for (int neighbor : neighbors) {
                    if (neighbor != -1 && !infected[neighbor]) {
                        infected[neighbor] = true;
                        queue.offer(neighbor);
                        spreadHappened = true;
                    }
                }
            }
            
            // 如果这一轮没有新感染，且还有未感染区域，说明无法扩散完全
            if (!spreadHappened) {
                break;
            }
            steps++;
        }

        // 检查是否全部感染
        boolean allInfected = true;
        for (boolean b : infected) {
            if (!b) {
                allInfected = false;
                break;
            }
        }
        
        System.out.println(allInfected ? steps : -1);
    }
}

这段代码里最关键的逻辑在于 while 循环内部。我们使用 size 变量来锁定当前层的节点数量，确保每一轮只处理同一时间步产生的影响。每次从队列取出一个点，计算它的四个合法邻居，如果邻居未被感染，就标记并加入队列。这样自然形成了层级推进的效果。

实际运行时会遇到一种情况：初始地图全为 0，或者某些区域被 0 隔断导致永远无法感染。代码最后做了一个全图检查，如果存在未感染单元格，返回 -1 表示无解。对于 3x3 这种小规模数据，这个方案效率很高，空间占用也极小。如果是更大的网格，可以考虑使用位运算优化状态存储，但逻辑框架是一样的。