Practice › Graphs
Rotting Oranges
Medium · Graphs · Asked at Amazon, Microsoft, Google
Grid cells are 0 (empty), 1 (fresh orange) or 2 (rotten). Every minute, fresh oranges next to a rotten one (up/down/left/right) become rotten. Print the minutes until no fresh orange is left, or -1 if that never happens.
Input
First line: r c. Next r lines: c values.
Output
The minutes needed, or -1.
Constraints
- 1 ≤ r, c ≤ 300
Multi-source BFS starting from all rotten oranges at once.
Example 1
Input
3 3 2 1 1 1 1 0 0 1 1
Output
4
Example 2
Input
3 3 2 1 1 0 1 1 1 0 1
Output
-1
Hints
- All rotten oranges spread at the same time — start a BFS from every one of them together.
- Process the queue minute by minute (level by level). At the end, any fresh orange left means −1.
Approach
Multi-source BFS. Put every rotten orange in the queue and count the fresh ones. Each round (one minute) pops the whole current level and rots its fresh neighbours, pushing them for the next round. Count only rounds that actually rotted something. If fresh oranges remain at the end, some are unreachable, so print -1. With no fresh oranges at all, the answer is 0.
Complexity: O(r·c) time · O(r·c) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int r, c;
cin >> r >> c;
vector<vector<int>> g(r, vector<int>(c));
queue<pair<int, int>> q;
int fresh = 0;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) {
cin >> g[i][j];
if (g[i][j] == 2) q.push({i, j});
if (g[i][j] == 1) fresh++;
}
int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
int minutes = 0;
while (!q.empty() && fresh > 0) {
int size = q.size();
for (int k = 0; k < size; k++) {
auto cell = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int x = cell.first + dr[d], y = cell.second + dc[d];
if (x >= 0 && x < r && y >= 0 && y < c && g[x][y] == 1) {
g[x][y] = 2;
fresh--;
q.push({x, y});
}
}
}
minutes++;
}
cout << (fresh == 0 ? minutes : -1) << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
r, c = data[0], data[1]
g = [data[2 + i * c : 2 + (i + 1) * c] for i in range(r)]
level = [(i, j) for i in range(r) for j in range(c) if g[i][j] == 2]
fresh = sum(row.count(1) for row in g)
minutes = 0
while level and fresh:
nxt = []
for x, y in level:
for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
if 0 <= nx < r and 0 <= ny < c and g[nx][ny] == 1:
g[nx][ny] = 2
fresh -= 1
nxt.append((nx, ny))
level = nxt
minutes += 1
print(minutes if fresh == 0 else -1)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int r = sc.nextInt(), c = sc.nextInt();
int[][] g = new int[r][c];
ArrayDeque<int[]> q = new ArrayDeque<>();
int fresh = 0;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) {
g[i][j] = sc.nextInt();
if (g[i][j] == 2) q.add(new int[] {i, j});
if (g[i][j] == 1) fresh++;
}
int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
int minutes = 0;
while (!q.isEmpty() && fresh > 0) {
int size = q.size();
for (int k = 0; k < size; k++) {
int[] cell = q.poll();
for (int d = 0; d < 4; d++) {
int x = cell[0] + dr[d], y = cell[1] + dc[d];
if (x >= 0 && x < r && y >= 0 && y < c && g[x][y] == 1) {
g[x][y] = 2;
fresh--;
q.add(new int[] {x, y});
}
}
}
minutes++;
}
System.out.println(fresh == 0 ? minutes : -1);
}
}