Final: Spreading Rot

Lab C++ Advanced 30 points

A crate grid holds 2 (rotten), 1 (fresh) and 0 (empty). Each minute, rotten oranges rot their fresh neighbours (up/down/left/right). Print the minutes until nothing fresh is left, or -1 if some never rot. Use BFS from all rotten oranges at once.

Input

Line 1: rows cols. Then the grid, numbers separated by spaces.

Output

One number.

Example

Input

Output

Sample input available Sample output available

Editor

C++

Hints

Push every rotten orange with time 0 first.

A neighbour rotted at time t + 1.

Count fresh oranges; any left means -1.

Solution explanation

Multi-source BFS spreads from all starting points together.

Show solution

#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;

int main() {
    int R, C;
    cin >> R >> C;
    vector<vector<int>> g(R, vector<int>(C));
    queue<tuple<int, int, int>> q;
    int fresh = 0;
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++) {
            cin >> g[r][c];
            if (g[r][c] == 2) q.push({r, c, 0});
            else if (g[r][c] == 1) fresh++;
        }
    int minutes = 0;
    int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
    while (!q.empty()) {
        auto [r, c, t] = q.front();
        q.pop();
        minutes = max(minutes, t);
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr >= 0 && nr < R && nc >= 0 && nc < C && g[nr][nc] == 1) {
                g[nr][nc] = 2;
                fresh--;
                q.push({nr, nc, t + 1});
            }
        }
    }
    cout << (fresh == 0 ? minutes : -1) << endl;
    return 0;
}

Output

Answer