package 宽度优先搜索;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class Code_bfs4腐烂的橘子 {
static class demo{ // 橘子类 也可以称为点类
public int x;
public int y;
public demo(int x, int y){
this.x = x;
this.y = y;
}
public demo() {
}
}
static Queue<demo> q = new LinkedList<demo>(); // 以队列为泛型的队列存放橘子的点位
public static int orangesRotting(int[][] grid) {
int res = -1;
int a = grid.length;
int b = grid[0].length;
Set<demo> vis = new HashSet<demo>(); // 用来存放已经走过的点
boolean f = true; // 如果这个数组中根本就不存在新鲜的橘子直接返回0
for(int i = 0; i < a; i++) {
for(int j = 0; j < b; j++) {
if(grid[i][j] == 2) {
demo d = new demo(i, j); // 这里是最坑的一个点只能重新new 不能放在循环的外面
q.add(d);
vis.add(d);
}
if(grid[i][j] == 1) {
f = false;
}
}
}
// 扫描整个数组将有坏橘子的点记录下来放到队列中因为是bfs所以即使存在多个坏的橘子也能在一次循环中解决
// 多个坏橘子的点会依次往外扩
if(f == true) {
return 0;
}
res = bfs(vis, grid);
return res;
}
public static int bfs(Set<demo> vis, int[][] grid) {
int step = 0;
demo dx = new demo();
while(!q.isEmpty()) {
step++;
int size = q.size();
for(int a = 0; a < size; a++) {
dx = q.peek(); // 拿出队头的坏橘子
int x = dx.x;
int y = dx.y; // 记录他们的坐标然后往上，下，左，右四个方向感染
// 往上走
if(x + 1 >= 0 && x + 1 < grid.length && grid[x + 1][y] == 1) {
demo d1 = new demo(x + 1, y);
if(!vis.contains(d1)) {
q.add(d1);
vis.add(d1); // 找到了新鲜的橘子就将其标记
grid[x + 1][y] = 2;
}
}
// 往下走
if(x - 1 >= 0 && x - 1 < grid.length && grid[x - 1][y] == 1) {
demo d2 = new demo(x - 1, y);
if(!vis.contains(d2)) {
q.add(d2);
vis.add(d2);
grid[x - 1][y] = 2;
}
}
// 往右走
if(y + 1 >= 0 && y + 1 < grid[0].length && grid[x][y + 1] == 1) {
demo d3 = new demo(x, y + 1);
if(!vis.contains(d3)) {
q.add(d3);
vis.add(d3);
grid[x][y + 1] = 2;
}
}
// 往左走
if(y - 1 >= 0 && y - 1 < grid[0].length && grid[x][y - 1] == 1 ) {
demo d4 = new demo(x, y - 1);
if(!vis.contains(d4)) {
q.add(d4);
vis.add(d4);
grid[x][y - 1] = 2;
}
}
q.poll(); // 出队
}
}
for(int a = 0; a < grid.length; a++) {
for(int b = 0; b < grid[0].length; b++) {
if(grid[a][b] == 1) {
return -1;
}
}
}
return step - 1;
// 这里step-1的原因是最后一批在队列中的橘子是被前一批橘子感染的又因为这最后一批已经没有
// 新鲜橘子可感染了但是之前step已经++过了所以我们要在这里减一个1
}
public static void main(String[] args) {
int[][] grid = {
{1,2,1,1,2,1,1}
};
int res = orangesRotting(grid);
System.out.println(res);
}
// 我们再来看一下leetcode上大牛的代码
/*
他的代码的整体思路是i从2开始也就是第一个坏橘子开始, 然后往上下左右四个方向走
找到新鲜橘子了就将这个新鲜橘子的点的值变成 i+1 然后i++就相当于i又从i+1开始找
找到了就将点标记成 i+1 知道找不到点 整个循环遍历完之后 i - 3就是结果因为i从2开始的
而且最后一次已经没有点了但是i还是加加了一次所以还需要减一次*/
public int orangesRotting1(int[][] grid) {
int key = 1;
int i;
for (i = 2; key == 1; i++) {
key = 0;
for (int j = 0; j < grid.length; j++) {
for(int k = 0; k < grid[0].length; k++)
{
if(grid[j][k] == i)
{
if(j + 1 < grid.length && grid[j + 1][k] == 1)
{
grid[j + 1][k] = i + 1;
key = 1;
}
if(k + 1 < grid[0].length && grid[j][k + 1] == 1)
{
grid[j][k + 1] = i + 1;
key = 1;
}
if(k - 1 >= 0 && grid[j][k - 1] == 1)
{
grid[j][k -1] = i + 1;
key = 1;
}
if(j - 1 >= 0 && grid[j - 1][k] == 1)
{
grid[j - 1][k] = i + 1;
key = 1;
}
}
}
}
}
for (int j = 0; j < grid.length; j++) {
for (int k = 0; k < grid[0].length; k++) {
if(grid[j][k] == 1)
{
return -1;
}
}
}
return i - 3;
}
}
