一僻澎、題目
在給定的 m x n 網(wǎng)格 grid 中貌踏，每個(gè)單元格可以有以下三個(gè)值之一：
- 值
0代表空單元格；- 值
1代表新鮮橘子窟勃；- 值
2代表腐爛的橘子祖乳。
每分鐘，腐爛的橘子 周圍 4 個(gè)方向上相鄰 的新鮮橘子都會(huì)腐爛秉氧。
返回直到單元格中沒有新鮮橘子為止所必須經(jīng)過的最小分鐘數(shù)凡资。如果不可能，返回 -1 谬运。
二、示例
2.1> 示例 1：
【輸入】grid = [[2,1,1],[1,1,0],[0,1,1]]
【輸出】4
2.2> 示例 2：
【輸入】grid = [[2,1,1],[0,1,1],[1,0,1]]
【輸出】-1
【解釋】左下角的橘子（第 2 行垦藏， 第 0 列）永遠(yuǎn)不會(huì)腐爛梆暖，因?yàn)楦癄€只會(huì)發(fā)生在 4 個(gè)正向上。
2.3> 示例 3：
【輸入】grid = [[0,2]]
【輸出】0
【解釋】因?yàn)?0 分鐘時(shí)已經(jīng)沒有新鮮橘子了掂骏，所以答案就是 0 轰驳。
提示：
- m == grid.length
- n == grid[i].length
-
1<= m, n <=10 - grid[i][j] 僅為
0、1或2
三弟灼、解題思路
根據(jù)題目描述级解，我們要計(jì)算出單元格中沒有新鮮橘子為止所必須經(jīng)過的最小分鐘數(shù)。由于腐爛的橘子可以將好的橘子也變腐爛田绑，所以勤哗，我們需要采用某種方式，將這種橘子腐爛的輪次模擬計(jì)算出來掩驱。
這里芒划，我們首先創(chuàng)建一個(gè)隊(duì)列冬竟，即：Deque。然后先將矩陣中腐爛的橘子保存到deque中民逼。然后獲取deque中存儲的腐爛橘子的個(gè)數(shù)num泵殴，那么當(dāng)num個(gè)橘子從deque中出棧之后，就表示該輪次執(zhí)行完畢拼苍。
那么笑诅，當(dāng)我們從隊(duì)列deque中彈出腐爛的橘子之后，我們會(huì)將該爛橘子的上疮鲫、下吆你、左、右的新鮮橘子都變?yōu)闋€橘子棚点，即：grid[x][y] = 2早处。然后將剛剛變爛的句子放入到deque中，準(zhǔn)備作為后續(xù)下一輪需要操作的爛橘子瘫析。
那么砌梆，需要補(bǔ)充一點(diǎn)的就是，當(dāng)我們計(jì)算矩陣中腐爛橘子的同時(shí)贬循，也可以同時(shí)獲得新鮮的橘子的個(gè)數(shù)fresh咸包，當(dāng)面當(dāng)我們發(fā)現(xiàn)fresh等于0的時(shí)候，則說明所有的好橘子都被腐爛了杖虾，返回操作的輪次數(shù)烂瘫；而當(dāng)我們操作完所有的腐爛橘子，而fresh依然不為0奇适，則說明某些新鮮的橘子是不會(huì)被傳染腐爛的坟比，則直接返回-1即可。
以上就是本題的解題思路嚷往。為了方便大家理解葛账，請參照下圖圖解即可：
四、代碼實(shí)現(xiàn)
class Solution {
int fresh = 0, minute = 0;
Deque<int[]> deque = new ArrayDeque();
public int orangesRotting(int[][] grid) {
int result = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 2) deque.addLast(new int[]{i, j});
if (grid[i][j] == 1) fresh++;
}
}
while (fresh > 0 && !deque.isEmpty()) {
minute++;
int nums = deque.size();
for (int i = 0; i < nums; i++) {
int[] cell = deque.removeFirst();
int x = cell[0], y = cell[1];
rot(grid, x - 1, y); // 查看上方單元格
rot(grid, x + 1, y); // 查看下方單元格
rot(grid, x, y - 1); // 查看左側(cè)單元格
rot(grid, x, y + 1); // 查看右側(cè)單元格
}
}
return fresh > 0 ? -1 : minute;
}
public void rot(int[][] grid, int x, int y) {
if (x >= 0 && y >=0 && x < grid.length && y < grid[0].length && grid[x][y] == 1) {
grid[x][y] = 2;
deque.addLast(new int[]{x, y});
fresh--;
}
}
}
今天的文章內(nèi)容就這些了：
寫作不易皮仁，筆者幾個(gè)小時(shí)甚至數(shù)天完成的一篇文章籍琳，只愿換來您幾秒鐘的 點(diǎn)贊 & 分享 。
更多技術(shù)干貨贷祈，歡迎大家關(guān)注公眾號“爪哇繆斯” ~ \(o)/ ~ 「干貨分享趋急，每天更新」
