994 Rotting Oranges 腐爛的橘子
Description:
In a given grid, each cell can have one of three values:
the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.
Example:
Example 1:
Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:
Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
Example 3:
Input: [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Note:
1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] is only 0, 1, or 2.
題目描述:
在給定的網(wǎng)格中椿访，每個(gè)單元格可以有以下三個(gè)值之一：
值 0 代表空單元格油湖；
值 1 代表新鮮橘子瓦阐；
值 2 代表腐爛的橘子蚁署。
每分鐘鲤拿，任何與腐爛的橘子（在 4 個(gè)正方向上）相鄰的新鮮橘子都會(huì)腐爛。
返回直到單元格中沒(méi)有新鮮橘子為止所必須經(jīng)過(guò)的最小分鐘數(shù)歼疮。如果不可能杂抽，返回 -1。
示例 :
示例 1：
輸入：[[2,1,1],[1,1,0],[0,1,1]]
輸出：4
示例 2：
輸入：[[2,1,1],[0,1,1],[1,0,1]]
輸出：-1
解釋：左下角的橘子（第 2 行韩脏， 第 0 列）永遠(yuǎn)不會(huì)腐爛缩麸，因?yàn)楦癄€只會(huì)發(fā)生在 4 個(gè)正向上。
示例 3：
輸入：[[0,2]]
輸出：0
解釋：因?yàn)?0 分鐘時(shí)已經(jīng)沒(méi)有新鮮橘子了赡矢，所以答案就是 0 杭朱。
提示：
1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] 僅為 0、1 或 2
思路:
遍歷橘子, 將腐爛的橘子加入隊(duì)列, 并記錄橘子的數(shù)量. 采用 BFS的思想遍歷隊(duì)列, 每次對(duì) 4個(gè)方向的橘子進(jìn)行腐爛, 直到隊(duì)列為空. 如果所有橘子都腐爛, 返回遍歷的次數(shù), 否則返回 -1
時(shí)間復(fù)雜度O(n ^ 2), 空間復(fù)雜度O(n ^ 2)
代碼:
C++:
class Solution
{
public:
int orangesRotting(vector<vector<int>>& grid)
{
queue<pair<int, int>> q;
vector<pair<int, int>> directs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int count = 0, result = -1, row = grid.size(), col = grid[0].size();
for (int i = 0; i < row; i++) for (int j = 0; j < col; j++)
{
if (grid[i][j] == 2) q.push(make_pair(i, j));
if (grid[i][j]) ++count;
}
if (q.size() == count) return 0;
while (q.size())
{
int s = q.size();
while (s--)
{
auto cur = q.front();
q.pop();
count--;
for (auto direct : directs)
{
int x = cur.first + direct.first, y = cur.second + direct.second;
if (x < 0 or y < 0 or x > row - 1 or y > col - 1 or grid[x][y] != 1) continue;
grid[x][y] = 2;
q.push(make_pair(x, y));
}
}
++result;
}
return count ? -1 : result;
}
};
Java:
class Solution {
public int orangesRotting(int[][] grid) {
Queue<Integer> q = new LinkedList<>();
int dx[] = new int[]{1, 0, -1, 0}, dy[] = new int[]{0, 1, 0, -1}, row = grid.length, col = grid[0].length, count = 0, result = -1;
for (int i = 0; i < row; i++) for (int j = 0; j < col; j++) {
if (grid[i][j] == 2) q.offer((i + 1 << 4) + j);
if (grid[i][j] > 0) count++;
}
if (q.size() == count) return 0;
while (!q.isEmpty()) {
int s = q.size();
while (s-- > 0) {
int cur = q.poll();
count--;
for (int k = 0; k < 4; k++) {
int x = dx[k] + (cur >> 4) - 1, y = dy[k] + (cur & 15);
if (x < 0 || y < 0 || x > row - 1 || y > col - 1 || grid[x][y] != 1) continue;
grid[x][y] = 2;
q.offer((x + 1 << 4) + y);
}
}
result++;
}
return count == 0 ? result : -1;
}
}
Python:
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
queue, row, col, count, result, directs = [], len(grid), len(grid[0]), 0, -1, [(1, 0), (0, 1), (-1, 0), (0, -1)]
for i in range(row):
for j in range(col):
if grid[i][j]:
count += 1
if grid[i][j] == 2:
queue.append((i, j))
if count == len(queue):
return 0
while queue:
s = len(queue)
while s:
cur = queue.pop(0)
count -= 1
for direct in directs:
x, y = direct[0] + cur[0], direct[1] + cur[1]
if -1 < x < row and -1 < y < col and grid[x][y] == 1:
grid[x][y] = 2
queue.append((x, y))
s -= 1
result += 1
return -1 if count else result
