# LeetCode - 0994. Rotting Oranges
### 題目網址：https://leetcode.com/problems/rotting-oranges/
###### tags: `LeetCode` `Medium` `廣度優先搜尋（Breadth First Search）`

/*
    -LeetCode format-
    Problem: 994. Rotting Oranges
    Difficulty: Medium
    
    by Inversionpeter
*/



#define WITHIN(row, column) (0 <= row && row < grid.size() && 0 <= column && column < grid[0].size())


const int dr[4] = { -1, 0, 1, 0 }, dc[4] = { 0, 1, 0, -1 };

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int fresh = 0, maximumMinutes = 0, nowRow, nowColumn, nowMinute, newRow, newColumn;
        queue <vector <int>> rotten;
        for (int i = 0; i != grid.size(); ++i)
            for (int j = 0; j != grid[0].size(); ++j)
                switch (grid[i][j]) {
                    case 1:
                        ++fresh;
                        break;
                    case 2:
                        rotten.push({ i, j, 0 });
                        break;
                }
        while (!rotten.empty()) {
            nowRow = rotten.front()[0]; nowColumn = rotten.front()[1]; nowMinute = rotten.front()[2]; rotten.pop();
            maximumMinutes = max(maximumMinutes, nowMinute);
            for (int i = 0; i < 4; ++i) {
                newRow = nowRow + dr[i]; newColumn = nowColumn + dc[i];
                if (WITHIN(newRow, newColumn) && grid[newRow][newColumn] == 1) {
                    rotten.push({ newRow, newColumn, nowMinute + 1 });
                    grid[newRow][newColumn] = 2;
                    --fresh;
                }
            }
        }
        return (!fresh ? maximumMinutes : -1);
    }
};