題目網址：https://leetcode.cn/problems/rotting-oranges/

題意：給一 m x n 的網格 grid, 其中每個 cell 有三種可能：

  • 0 代表沒橘子
  • 1 代表新鮮橘子
  • 2 代表腐爛的橘子

每分鐘, 腐爛的橘子周圍 4 個方向上相鄰的新鮮橘子都會腐爛。

返回 grid 中沒有新鮮橘子所必須經過的最短時間。如果不可能, 則返回 -1 。

Solution：

想法：利用 BFS, 因為 grid 一開始可能有多顆腐爛的橘子

typedef pair<int, int> pii;

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();

        int res = 0, fresh = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    ++fresh;
                } else if (grid[i][j] == 2) {
                    q.emplace(pii{i, j});
                }
            }
        }

        bfs(grid, res, fresh);

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return res;
    }

private:
    int m, n;
    queue<pii> q;
    vector<pii> dirs = {
        {0, 1}, {0, -1},
        {1, 0}, {-1, 0}
    };

    void bfs(vector<vector<int>>& grid, int& res, int& fresh){
        // 一旦沒有新鮮的橘子即可退出
        while (!q.empty() && fresh > 0) {
            for (int k = q.size(); k > 0; --k) {
                const auto [y, x] = q.front();
                q.pop();

                for (const auto& [dirY, dirX] : dirs) {
                    const int r = y + dirY, c = x + dirX;
                    if (!outOfBound(r, c) && grid[r][c] == 1) {
                        --fresh;
                        grid[r][c] = 2;
                        q.emplace(pii{r, c});
                    }
                }
            }
            ++res;
        }
    }

    bool outOfBound(const int i, const int j){
        if (i < 0 || i == m || j < 0 || j == n) {
            return true;
        }
        return false;
    }
};
  • time：$O(m \cdot n)$ ➔ 遍歷 grid
  • space：$O(m \cdot n)$ ➔ q 中的元素個數不超過 m * n, worse case：grid 元素皆為 2