994. Rotting Oranges

 In a given grid, each cell can have one of three values:

• the value 0 representing an empty cell;
• the value 1 representing a fresh orange;
• the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) 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 instead.

 

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

 

Note:

1. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. grid[i][j] is only 0, 1, or 2.

class Solution {

public:

    bool valid(vector<vector<int>>& grid, int new_x, int new_y) {

        if (new_x < 0 || new_x >= grid.size() || new_y < 0 || new_y >= grid[0].size()) {

            return false;

        }

        return true;

    }

    int orangesRotting(vector<vector<int>>& grid) {

        int fresh_count = 0;

        queue<pair<int,int>> q;

        int rows = grid.size();

        if (rows == 0) {

            return 0;

        }

        int cols = grid[0].size();

        for (int i = 0; i < rows; i++) {

            for (int j = 0; j < cols; j++) {

                if (grid[i][j] == 1) {

                    fresh_count++;

                } else if (grid[i][j] == 2) {

                    q.push({i, j});

                }

            }

        }

        

        vector<vector<bool>> visited(rows, vector<bool>(cols, false));

        vector<vector<int>> neighbors = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        int ans = 0;

        int rotten = 0;

        while (!q.empty()) {

            int size = q.size();

            if (size == 0) {

                break;

            }

            for (int i = 0; i < size; i++) {

                pair<int, int> rotten_node = q.front(); q.pop();

                for (auto neighbor : neighbors) {

                    int new_x = rotten_node.first + neighbor[0];

                    int new_y = rotten_node.second + neighbor[1];

                    if (valid(grid, new_x, new_y) && !visited[new_x][new_y] &&

                       grid[new_x][new_y] == 1) {

                        rotten++;

                        grid[new_x][new_y] = 2;

                        q.push({new_x, new_y});

                        visited[new_x][new_y] = true;

                    }

                }

            }

            ans++;

        }

        if (rotten == fresh_count) {

            return ans != 0 ? ans - 1 : 0;

        }

        return -1;

    }

};