宽度优先搜索
感染区就相当于我们往水面扔了一颗石子,广度优先搜索就相当于荡起的一圈涟漪
而二叉树的 BFS 是只会向左右2侧泛起涟漪!!!
import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static boolean[][] isVisited;
static Deque<Integer[]> deque = new ArrayDeque<>();
static int N;
static int[][] arr;
static int res;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] str = in.nextLine().split(",");
N = str.length;
int count = (int) Math.pow(N, 0.5);
isVisited = new boolean[count][count];
arr = new int[count][count];
int index = 0;
int startWeak = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
arr[i][j] = Integer.parseInt(str[index++]);
if (arr[i][j] == 1){
isVisited[i][j] = true;
deque.offer(new Integer[]{i, j});
startWeak++;
}
}
}
if (startWeak == 0 || startWeak == N){
System.out.println(-1);
return;
}
bfs();
System.out.println(res - 1);
}
public static void bfs(){
while (!deque.isEmpty()) {
int size = deque.size();
while (size > 0) {
Integer[] peek = deque.poll();
turnWeak(peek[0], peek[1]);
size--;
}
res++;
}
}
public static void turnWeak(int i, int j){
if (i - 1 >= 0 && !isVisited[i - 1][j]){ // 上
deque.offer(new Integer[]{i - 1, j});
isVisited[i - 1][j] = true;
}
if (i + 1 < Math.sqrt(N) && !isVisited[i + 1][j]){ // 下
deque.offer(new Integer[]{i + 1, j} );
isVisited[i + 1][j] = true;
}
if (j - 1 >= 0 && !isVisited[i][j - 1]){ // 左
deque.offer(new Integer[]{i, j - 1} );
isVisited[i][j - 1] = true;
}
if (j + 1 < Math.sqrt(N) && !isVisited[i][j + 1]){
deque.offer(new Integer[]{i, j + 1} );
isVisited[i][j + 1] = true;
}
}
}