994. Rotting Oranges
You are given an m x n grid where each cell can have one of three values:
- 0 representing an empty cell,
- 1 representing a fresh orange, or
- 2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent 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.
Example 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:
Input: grid = [[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: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10
- grid[i][j] is 0, 1, or 2.
From: LeetCode
Link: 994. Rotting Oranges
Solution:
Ideas：
The function counts the number of fresh oranges and enqueues the positions of the rotten oranges. It then uses BFS to iterate through the grid, rotting adjacent fresh oranges each minute. If there are no fresh oranges left, it returns the number of minutes that have passed. If there are still fresh oranges that cannot be reached, it returns -1.
Code:
int orangesRotting(int** grid, int gridSize, int* gridColSize) {
int fresh = 0;
int minutes = 0;
int directions[4][2] = {
{
-1, 0}, {
1, 0}, {
0, -1}, {
0, 1}};
int currentSize, i, j, k, x, y;
// Count fresh oranges and enqueue rotten oranges' positions
int queueSize = gridSize * (*gridColSize);
int **queue = malloc(queueSize * sizeof(int*));
for (i = 0; i < queueSize; i++) {
queue[i] = malloc(2 * sizeof(int));
}
int front = 0, rear = 0;
for (i = 0; i < gridSize; i++) {
for (j = 0; j < gridColSize[i]; j++) {
if (grid[i][j] == 1) {
fresh++;
} else if (grid[i][j] == 2) {
queue[rear][0] = i;
queue[rear][1] = j;
rear++;
}
}
}
// BFS from rotten oranges
while (fresh > 0 && front < rear) {
currentSize = rear - front; // Number of oranges to rot this minute
for (k = 0; k < currentSize; k++) {
int *point = queue[front++];
for (i = 0; i < 4; i++) {
x = point[0] + directions[i][0];
y = point[1] + directions[i][1];
if (x >= 0 && y >= 0 && x < gridSize && y < gridColSize[x] && grid[x][y] == 1) {
grid[x][y] = 2;
queue[rear][0] = x;
queue[rear][1] = y;
rear++;
fresh--;
}
}
}
minutes++;
}
// Free memory
for (i = 0; i < queueSize; i++) {
free(queue[i]);
}
free(queue);
return fresh == 0 ? minutes : -1;
}
