计算疫情扩散时间

该专栏题目包含两部分：
100 分值部分题目
200 分值部分题目
所有题目都会陆续更新，订阅防丢失

题目描述

在一个地图中(地图由 $N\ast N$ 个区域组成)，有部分区域被感染病菌。

感染区域每天都会把周围(上下左右)的4个区域感染。

请根据给定的地图计算，多少天以后，全部区域都会被感染。

如果初始地图上所有区域全部都被感染，或者没有被感染区域，返回-1

输入描述

• 行 $N\ast N$ 个数字(只包含0，1，不会有其他数字)表示一个地图，数字间用","分割

• 0 表示未感染区域

• 1表示已经感染区域

每 $N$ 个数字表示只地图中一行，输入数据共表示 $N$ 行 $N$ 列的区域地图。例如输入:

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

表示地图
$\left[\begin{array}{ccc}1& 0& 1\\ 0& 0& 0\\ 1& 0& 1\end{array}\right]$

输出描述

1个整数，表示经过多少天以后，全部区域都被感染

数据范围

• $1\le 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

说明

全部都感染

题解

BFS 使用广度优先算法求解

源码 Java

import java.util.ArrayList;
import java.util.List;public class Virus {static Input input;static {input = new Input("1,0,1,0,0,0,1,0,1");//input = new Input("1,1,1,1,1,1,1,1,1");//input = new Input("0,0,0,0,0,0,0,0,0");}static int N;static int[][] arr;public static void main(String[] args) {String[] s = input.nextLine().split(",");int n = (int)Math.sqrt(s.length);N = n;arr = new int[n][n];int index = 0;List<Point> list = new ArrayList<>();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {int i1 = Integer.parseInt(s[index++]);if (1 == i1) {list.add(new Point(i, j));}arr[i][j] = i1;}}if (list.size() == 0 || list.size() == s.length){System.out.println(-1);} else {System.out.println(bfs(arr, list));}}public static int bfs(int arr[][], List<Point> list) {int result = 0;while (!list.isEmpty()) {result++;int size = list.size();List<Point> temp = new ArrayList<>();for (int i = 0; i < size; i++) {Point point = list.get(i);if (isCleanArea(point.x - 1, point.y)) {temp.add(new Point(point.x - 1, point.y));arr[point.x - 1][point.y] = 1;}if (isCleanArea(point.x + 1, point.y)) {temp.add(new Point(point.x + 1, point.y));arr[point.x + 1][point.y] = 1;}if (isCleanArea(point.x, point.y - 1)) {temp.add(new Point(point.x, point.y - 1));arr[point.x][point.y - 1] = 1;}if (isCleanArea(point.x, point.y + 1)) {temp.add(new Point(point.x, point.y + 1));arr[point.x][point.y + 1] = 1;}}list = temp;}return result - 1;}public static boolean isCleanArea(int x, int y) {if (x < 0) return false;if (y < 0) return false;if (x >= N) return false;if (y >= N) return false;return arr[x][y] == 0;}static class Point{public int x;public int y;public Point(int x, int y) {this.x = x;this.y = y;}}}