■ 题目描述
输入一行字符串，字符串可转换为N*N的数组，数组可认为是一个水域，判断多少天后，水域被全部污染。
数组中只有0和1，0表示纯净，1表示污染，每天只可污染上下左右的水域，如果开始全部被污染，或永远无法污染，则返回-1。
例如
示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入
1,0,1,0,0,0,1,0,1
全选代码
复制
转化为数组为：
1 0 1
0 0 0
1 0 1
输出：
2
全选代码
复制
样例解释
第一天后水域变为
1 1 1
1 0 1
1 1 1
第二天全部被污染
输入
0,0,0,0
全选代码
复制
输出
-1
public class PolluteWater {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] s = sc.nextLine().split(",");
int N = (int) Math.sqrt(s.length);
int[][] grid = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
grid[i][j] = Integer.parseInt(s[j + i * N]);
}
}
// 图的多源BFS
int[] dx = new int[]{0, 0, 1, -1};
int[] dy = new int[]{1, -1, 0, 0};
Queue<int[]> queue = new ArrayDeque<>();
// 将所有污染源都入队
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});
}
}
}
// 全部被无污染或者永远无法被污染
if (queue.size() == 0 || queue.size() == N * N) {
System.out.println(-1);
return;
}
// 从各个污染源开始，一圈圈遍历
int[] node = null; // 定义到循环外面，方便输出结果
while (!queue.isEmpty()){
node = queue.poll();
int x = node[0], y = node[1];
for (int i = 0; i < 4; i++) { // 上下左右扩散
int newX = x + dx[i];
int newY = y + dy[i];
// 越界或者不是净水
if (newX < 0 || newX >= N || newY < 0 || newY >= N || grid[newX][newY] != 0) {
continue;
}
// 直接修改原数组，把污染源改为净水
grid[newX][newY] = grid[x][y] + 1;
queue.offer(new int[]{newX, newY});
}
}
// 返回最后一次遍历到净水的天数 - 1，或者输出当前数组的最大值-1
System.out.println(grid[node[0]][node[1]] - 1);
}
}