leetcode-994

题目链接

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
  /**

* BFS

* @param grid

* @return

*/

public int orangesRotting(int[][] grid) {

// 存一下新鲜的橘子数量 curRot是当前时刻下对周围还有影响的坏橘子的数量,nextRot为下一时刻的对周围还有影响的坏橘子数量

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++;

​ }

​ }

​ }

// 特判 没有好橘子了 直接0

if (freshOrange == 0) return ans;

int i,j;

// 上下左右的方向值

int[] horizon = new int[] {0,0,-1,1};

int[] vertical = new int[] {-1,1,0,0};

// 开始BFS

// 其中curRot为0的时候,说明以及过了当前这一分钟了,也就说好橘子被感染的已经感染了

// nextRot就是用来记录在当前这一分钟后,有多少个好橘子被糟蹋了,并将这些变为坏橘子的标记入队,下一次就轮到他们去感染周围的橘子了

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++;

​ }

​ }

​ }

// 将时间加1

​ ans++;

​ curRot = nextRot;

​ nextRot = 0;

​ }

// 如果队列中没有可以在影响周围的坏橘子的时候,看看是否还有好橘子,如果有,说明那个好橘子的周围定没有坏橘子

// 这个周围是指他的上下左右

// 也就说这种情况,返回-1

if (freshOrange != 0) return -1;

return ans;

}


note:代码中队列入的是坏橘子的坐标,没重新定义类,直接加了两个Integer;curRot是用来判断一轮是不是结束了,一轮结束就意味着过来一分钟。