做淘宝一件代发的网站,网站流量的主要来源有,wordpress搭建视频教程,北京专业网站营销该专栏题目包含两部分#xff1a; 100 分值部分题目 200 分值部分题目 所有题目都会陆续更新#xff0c;订阅防丢失
题目描述
在一个地图中(地图由 N ∗ N N*N N∗N 个区域组成)#xff0c;有部分区域被感染病菌。
感染区域每天都会把周围(上下左右)的4个区域感染。
请…该专栏题目包含两部分 100 分值部分题目 200 分值部分题目 所有题目都会陆续更新订阅防丢失
题目描述
在一个地图中(地图由 N ∗ N N*N N∗N 个区域组成)有部分区域被感染病菌。
感染区域每天都会把周围(上下左右)的4个区域感染。
请根据给定的地图计算多少天以后全部区域都会被感染。
如果初始地图上所有区域全部都被感染或者没有被感染区域返回-1
输入描述 行 N ∗ N N*N N∗N 个数字(只包含01不会有其他数字)表示一个地图数字间用,分割 0 表示未感染区域 1表示已经感染区域
每 N N N 个数字表示只地图中一行输入数据共表示 N N N 行 N N N 列的区域地图。例如输入: 1,0,1,0,0,0,1,0,1 表示地图 [ 1 0 1 0 0 0 1 0 1 ] \begin{bmatrix} 101 \\ 000 \\ 101 \\ \end{bmatrix} 101000101
输出描述
1个整数表示经过多少天以后全部区域都被感染
数据范围 1 ≤ N 200 1≤N200 1≤N200
示例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;ListPoint 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[][], ListPoint list) {int result 0;while (!list.isEmpty()) {result;int size list.size();ListPoint 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;}}}
