LeetCode 994. Rotting Oranges

Problem

994. Rotting Oranges

Image is from Leetcode

It is a standard BFS problem. The difference of BFS to DFS is the BFS can get the shortest path.

The idea is

• Get the total number of fresh oranges first.
• Using the rotten orange to change the neighbor fresh orange to rotten orange by using the BFS.
• if we can change all the fresh orange to rotten orange, return the number of steps
• otherwise, fail, return -1.

Usually, for the BFS or DFS, we should maintain a seen or visited data structure to avoid visiting already visited nodes. For this problem, we can simply change the fresh to rotten, and then it will not be visited again.

C++ solution

const int FRESH = 1 , EMPTY = 0, ROTTEN = 2;
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) 
    {
        const int R = grid.size(), C = grid[0].size();
        int fresh = 0;
        queue<int> Q;
        for (int i = 0;  i < R; ++i)
            for (int j = 0; j < C; ++j)
                 {
                     if (grid[i][j] == FRESH) fresh++;
                     else if (grid[i][j] == ROTTEN) Q.push(i*C + j);
                 }
        if (fresh == 0) return 0;
        int fresh_to_rotten = 0;
        vector<pair<int, int>> dirs = {{0, 1},{0, -1},{1, 0},{-1, 0}};
        int ret = 0;
        while (!Q.empty())
        {
            ret++;
            int len = Q.size();
            for (int k = 0; k < len; ++k)
            {
                auto idx = Q.front(); Q.pop();
                int i = idx/C, j = idx % C;
                for (auto [di, dj] : dirs)
                {
                    auto r = i + di, c = j + dj;
                    if (r >=R || r < 0 || c>=C || c < 0)continue;
                    if (grid[r][c] != FRESH) continue;
                    grid[r][c] = ROTTEN;
                    Q.push(r*C + c);
                    fresh_to_rotten++;
                }  
            }
            if (fresh_to_rotten == fresh) return ret;
        }
        return -1;
    }
};

Python solution

I wrote this python solution long time ago and the logic is not as clear as the C++ version. Please take the C++ version as a reference.

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        fresh, rotten = set(), set()
        if not grid or not grid[0]:return -1
        R, C = len(grid), len(grid[0])
        for i in range(R):
            for j in range(C):
                if grid[i][j]==1:
                    fresh.add((i,j))
                elif grid[i][j]==2:
                    rotten.add((i,j))
        if not fresh:return 0
        if not rotten:return -1
        
        res = 0
        while rotten:
            res += 1
            new_rotten = set()
            for i,j in rotten:
                for di, dj in [(-1, 0),(1, 0),(0, 1),(0, -1)]:
                    r, c = i+di, j+dj
                    if (r,c) in fresh:
                        new_rotten.add((r,c))
            if not new_rotten:return -1
            fresh -= new_rotten
            rotten = new_rotten
            if not fresh:return res

Thanks for reading.