#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/*
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.
*/


int minutes(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    int fo = 0, temp; // fresh oranges

    vector<vector<int>> visited = grid;
    queue<pair<int,int>> qq;

    for (int i=0;i<m;i++) {
        for (int j=0;j<n;j++) {
            if (visited[i][j]==2) 
                qq.push({i, j});
            if (visited[i][j]==1)
                fo++;
        }   
    }

    if (fo==0) return 0; // no fresh oranges
    if (qq.empty()) return -1; // no rotten oranges

    int ans = -1;
    vector<vector<int>> dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    while (!qq.empty()) {
        temp = qq.size();
        while (temp--) {
            auto [x,y] = qq.front();
            qq.pop();
            for (auto it: dirs) {
                int i = x+it[0];
                int j = y+it[1];
                if (i>=0 && i<m && j>=0 && j<n && visited[i][j]==1) {
                    visited[i][j] = 2;
                    fo--;
                    qq.push({i,j});
                }
            }
        }
        ans++;
    }

    if (fo!=0) return -1;
    else return ans;

}


int main() {
    cout<<"Hello World!\n";
    vector<vector<int>> grid = {
        {0,0,0},
        {0,0,0},
        {0,0,0},
    };
    cout<<minutes(grid);
}