Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. All rotten oranges spread at the same time — start a BFS from every one of them together.
  2. 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);
    }
}

Solve Rotting Oranges online · All practice problems