1
class Solution {
2
 public:
3
  int orangesRotting(vector<vector<int>> &grid) {
4
    vector<int> dir = {-1, 0, 1, 0, -1}; // used for finding all 4 adjacent coordinates
5

6
    int m = grid.size();
7
    int n = grid[0].size();
8

9
    queue<pair<int, int>> q;
10
    int fresh = 0; // To keep track of all fresh oranges left
11
    for (int i = 0; i < m; i++)
12
      for (int j = 0; j < n; j++) {
13
        if (grid[i][j] == 2) q.push({i, j});
14
        if (grid[i][j] == 1) fresh++;
15
      }
16
    int ans = -1; // initialised to -1 since after each step we increment the
17
                  // time by 1 and initially all rotten oranges started at 0.
18
    while (!q.empty()) {
19
      int sz = q.size();
20
      while (sz--) {
21
        pair<int, int> p = q.front();
22
        q.pop();
23
        for (int i = 0; i < 4; i++) {
24
          int r = p.first + dir[i];
25
          int c = p.second + dir[i + 1];
26
          if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) {
27
            grid[r][c] = 2;
28
            q.push({r, c});
29
            fresh--; // decrement by 1 foreach fresh orange that now is rotten
30
          }
31
        }
32
      }
33
      ans++; // incremented after each minute passes
34
    }
35
    if (fresh > 0) return -1; // if fresh>0 that means there are fresh oranges left
36
    if (ans == -1)
37
      return 0; // we initialised with -1, so if there were no oranges it'd take
38
                // 0 mins.
39
    return ans;
40
  }
41
};