Leetcode 994. Rotting Oranges

[medium][Amazon]

Rotting Oranges - LeetCode

You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,
• 1 representing a fresh orange, or
• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] is 0, 1, or 2.

[First — DFS solution]

[Notes]

1. choose to use DFS or BFS
2. keep track of the time changing
3. trick — add 2 min and minus 2 min to not effect the original grid
4. trick — if we find a faster way to damage the grid, we would get rid of the old number.

[Second — BFS]

1. create Queue<int[]> for BFS
2. if queue is not empty, keep polling point from queue, and add for directions and see if there is any not rooted points
3. check if there is any fresh orange left