994. Rotting Oranges

解題思路

看出來是 BFS 後，就很好解了。

程式碼

struct P {
    int x;
    int y;
};
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<P> q1, q2;
        int minute = 0, dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
        for(int i=0; i<grid.size(); i++)
        {
            for(int j=0; j<grid[i].size(); j++)
            {
                if(grid[i][j] == 2)
                    q1.push({i, j});
            }
        }
        while(true)
        {
            while(!q1.empty())
            {
                for(int i=0; i<4; i++)
                {
                    int newX = q1.front().x+dx[i], newY = q1.front().y+dy[i];
                    if(0 <= newX && newX < grid.size() && 0 <= newY && newY < grid[0].size() && grid[newX][newY] == 1)
                    {
                        q2.push({newX, newY});            
                        grid[newX][newY] = 2;
                    }
                }
                q1.pop();
            }
            minute += 1;
            if(q2.empty()) break;
            swap(q1, q2);
        }
        for(int i=0; i<grid.size(); i++)
            for(int j=0; j<grid[i].size(); j++)
                if(grid[i][j] == 1)
                    return -1;

        return minute - 1;
    }
};