题目链接
https://leetcode-cn.com/problems/rotting-oranges/
思路
一开始看到题目感觉还挺有趣的,感觉像是小时候玩的小游戏。然后就有点迷,好像只能一个个去模拟一分钟一分钟下的情况,然后就觉得那就这样去模拟吧,然后就是BFS去模拟了。
简单的描述下我的思路:
首先,round 0,在0分钟时刻,找出所有的坏橘子入队,记下当前坏橘子的数量和好橘子的总数量。
然后,round 1,让所有坏橘子感染周围的好橘子,这个周围是指上下左右,让刚刚变成坏橘子的入队,之前的坏橘子全部出队,并且记录时间。
然后,round 2,一直循环感染,知道队列中没有可以进行感染的橘子或者好橘子都没了。
最后,ronnd 3,返回结果。
贴上代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
|
public int orangesRotting(int[][] grid) {
int freshOrange = 0,ans = 0,curRot = 0,nextRot = 0;
int row = grid.length;
int column = grid[0].length;
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if (grid[i][j] == 1) freshOrange++;
else if (grid[i][j] == 2) {
deque.add(i);
deque.add(j);
curRot++;
}
}
}
if (freshOrange == 0) return ans;
int i,j;
int[] horizon = new int[] {0,0,-1,1};
int[] vertical = new int[] {-1,1,0,0};
while (!deque.isEmpty() && freshOrange != 0) {
while (curRot != 0) {
i = deque.remove();
j = deque.remove();
curRot--;
for (int k = 0;k < 4;k++) {
int l = i+vertical[k];
int m = j+horizon[k];
if (l >= 0 && l < row && m >= 0 && m < column && grid[l][m] == 1){
grid[l][m] = 2;
freshOrange--;
deque.add(l);
deque.add(m);
nextRot++;
}
}
}
ans++;
curRot = nextRot;
nextRot = 0;
}
if (freshOrange != 0) return -1;
return ans;
}
|
note:代码中队列入的是坏橘子的坐标,没重新定义类,直接加了两个Integer;curRot是用来判断一轮是不是结束了,一轮结束就意味着过来一分钟。