Problem: 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:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
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.
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.
Approach: This is another BFS problem. We treat this matrix as graph where a cell is connected to another cell if they are neighbour of each other (except diagonal neighbours). We start our BFS with all the initial rotten oranges (grid[x][y] == 2) cells enqueued in a queue.
We keep incrementing the number of minutes at every iteration and make all the fresh oranges neighbours 2 (rotten). Once the BFS ends, we just need to check if there is a cell with fresh orange, if yes then we will return -1 otherwise we return the number of minutes.
Implementation in C#:
public int OrangesRotting(int[][] grid) {
int rows = grid?.Length ?? 0;
if (rows == 0)
{
return 0;
}
int cols = grid[0].Length;
Queue<int[]> queue = new Queue<int[]>();
int numOfFreshCells = this.GetFreshCellsAndAddRottenCellsToQueue(grid,
queue);
if (numOfFreshCells == 0)
{
return 0;
}
int minutes = 0;
while (queue.Count > 0)
{
int size = queue.Count;
for (int i = 0; i < size; ++i)
{
var cell = queue.Dequeue();
this.AddNeighbourFreshCellsToQueue(cell,
grid,
queue,
ref numOfFreshCells);
}
if (queue.Count > 0)
{
++minutes;
}
}
return numOfFreshCells != 0 ? - 1 : minutes;
}
private bool IsFreshCellRemaining(int[][] grid)
{
for (int i = 0; i < grid.Length; ++i)
{
for (int j = 0; j < grid[0].Length; ++j)
{
if (grid[i][j] == 1)
{
return true;
}
}
}
return false;
}
private void AddNeighbourFreshCellsToQueue(int[] cell,
int[][] grid,
Queue<int[]> queue,
ref int numOfFreshCells)
{
// Left cell
if (this.IsValidAndFreshCell(cell[0], cell[1] - 1, grid))
{
grid[cell[0]][cell[1] - 1] = 2;
queue.Enqueue(new int[] {cell[0], cell[1] - 1});
--numOfFreshCells;
}
// Right cell
if (this.IsValidAndFreshCell(cell[0], cell[1] + 1, grid))
{
grid[cell[0]][cell[1] + 1] = 2;
queue.Enqueue(new int[] {cell[0], cell[1] + 1});
--numOfFreshCells;
}
// Up cell
if (this.IsValidAndFreshCell(cell[0] - 1, cell[1], grid))
{
grid[cell[0] - 1][cell[1]] = 2;
queue.Enqueue(new int[] {cell[0] - 1, cell[1]});
--numOfFreshCells;
}
// Down cell
if (this.IsValidAndFreshCell(cell[0] + 1, cell[1], grid))
{
grid[cell[0] + 1][cell[1]] = 2;
queue.Enqueue(new int[] {cell[0] + 1, cell[1]});
--numOfFreshCells;
}
}
private bool IsValidAndFreshCell(int row, int col, int[][] grid)
{
return row >= 0 &&
row < grid.Length &&
col >= 0 &&
col < grid[0].Length &&
grid[row][col] == 1;
}
private int GetFreshCellsAndAddRottenCellsToQueue(int[][] grid,
Queue<int[]> queue)
{
int numOfFreshCells = 0;
for (int i = 0; i < grid.Length; ++i)
{
for (int j = 0; j < grid[0].Length; ++j)
{
if (grid[i][j] == 1)
{
++numOfFreshCells;
}
else if (grid[i][j] == 2)
{
queue.Enqueue(new int[] {i, j});
}
}
}
return numOfFreshCells;
}
Complexity: O(m x n) where m is number of rows and n is number of columns.
No comments:
Post a Comment