題目： LeetCode - 994. Rotting Oranges

題目說明

給一個二維陣列，裡面只含有 0、1、2。0 代表該座標沒有東西，1 代表該座標有一顆正常的橘子，2 代表該座標有一顆腐敗的橘子，腐敗的橘子每經過一天會使得上下左右四顆橘子也腐敗，求讓所有橘子都腐敗需要的天數，若無法使所有橘子腐敗就回傳 -1。

解題思路

先遍歷一次整個陣列，紀錄新鮮橘子的個數，腐敗橘子的座標使用 Queue 存放。接著把所有座標拿出並感染上下左右正常的橘子，再把新腐敗的橘子座標存入 Queue，清空一次 Queue 代表經過了一天，最後判斷是否還有未腐敗的橘子即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int height = grid.size(), width = grid[0].size(), fresh = 0, days = 0;
        int offset[] = {1, 0, -1, 0, 1};
        queue<pair<int, int>> _q;
        for(int i = 0; i < height; ++i) // y
            for(int j = 0; j < width; ++j) // x
                if(grid[i][j] == 1) ++fresh;
                else if(grid[i][j] == 2) _q.emplace(j, i);
        while(!_q.empty() && fresh)
        {
            int size = _q.size();
            while(size--)
            {
                int x = _q.front().first, y = _q.front().second;
                _q.pop();
                for(int i = 0; i < 4; ++i)
                {
                    int dx = x + offset[i], dy = y + offset[i + 1];
                    if(dx < 0 || dx >= width || dy < 0 || dy >= height || grid[dy][dx] != 1) continue;
                    --fresh;
                    grid[dy][dx] = 2;
                    _q.emplace(dx, dy);
                }
            }
            ++days;
        }
        return fresh ? -1 : days;
    }
};

2020-08-19 重寫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int height = grid.size(), width = grid[0].size(), fresh = 0, days = 0, size;
        int offset[] = {1, 0, -1, 0, 1};
        queue<pair<int, int>> q;
        for(int i = 0; i < height; ++i) for(int j = 0; j < width; ++j)
            if(grid[i][j] == 1) ++fresh; else if(grid[i][j] == 2) q.emplace(j, i);
        while((size = q.size()) && fresh && ++days) while(size--)
        {
            auto [x, y] = q.front(); q.pop();
            for(int i = 0; i < 4; ++i)
            {
                int dx = x + offset[i], dy = y + offset[i + 1];
                if(dx < 0 || dx >= width || dy < 0 || dy >= height || grid[dy][dx] != 1) continue;
                grid[dy][dx] = 2;
                --fresh;
                q.emplace(dx, dy);
            }
        }
        return fresh ? -1 : days;
    }
};