https://leetcode.com/problems/rotting-oranges/
Please review for coding style in 40 minutes job interview.
In a given grid, each cell can have one of three values:
the value 0 representing an empty cell; the value 1 representing a fresh orange; the value 2 representing a rotten orange. Every minute, any fresh orange that is adjacent (4-directionally) 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 instead.
Example 1: Input: [[2,1,1],[1,1,0],[0,1,1]] Output: 4 Example 2: Input: [[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: [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
Note:
- 1 <= grid.length <= 10
- 1 <= grid[0].length <= 10
- grid[i][j] is only 0, 1, or 2.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.Serialization.Formatters;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace GraphsQuestions
{
/// <summary>
/// https://leetcode.com/problems/rotting-oranges/
/// </summary>
[TestClass]
public class RottingOrangesTest
{
[TestMethod]
public void ExampleTest()
{
int[][] grid =
{
new []{2, 1, 1 },
new []{1, 1, 0},
new []{0, 1, 1}
};
Assert.AreEqual(4, RottingOrangesClass.OrangesRotting(grid));
}
[TestMethod]
public void BadExampleTest()
{
int[][] grid =
{
new []{2, 1, 1 },
new []{0, 1, 1},
new []{1, 0, 1}
};
Assert.AreEqual(-1, RottingOrangesClass.OrangesRotting(grid));
}
}
public class RottingOrangesClass
{
/// <summary>
/// we will use BFS and not DFS because we can move in one step to all of the directions.
/// not one by one and in this way we will get the best result
/// </summary>
/// <param name="grid"></param>
/// <returns></returns>
public static int OrangesRotting(int[][] grid)
{
if (grid == null || grid.Length == 0)
{
return 0;
}
int countFreshOranges = 0;
Queue<int[]> Q = new Queue<int[]>();
for (int row = 0; row < grid.Length; row++)
{
for (int col = 0; col < grid[0].Length; col++)
{
if (grid[row][col] == 2)
{
Q.Enqueue(new int[] { row, col }); // we save the rotten oranges
}
else if (grid[row][col] == 1)
{
countFreshOranges++; // we count the fresh oranges
}
}
}
if (countFreshOranges == 0)
{
return 0;
}
int count = 0;
while (Q.Count > 0)
{
count++;
int size = Q.Count;
for (int i = 0; i < size; i++)
{
int[] point = Q.Dequeue();
//try all directions
int x = point[0];
int y = point[1];
countFreshOranges = TryDirection(grid, x + 1, y, Q, countFreshOranges);
countFreshOranges = TryDirection(grid, x - 1, y, Q, countFreshOranges);
countFreshOranges = TryDirection(grid, x, y + 1, Q, countFreshOranges);
countFreshOranges = TryDirection(grid, x, y - 1, Q, countFreshOranges);
}
}
if (countFreshOranges == 0)
{
return count - 1;
}
return -1;
}
private static int TryDirection(int[][] grid, int x, int y, Queue<int[]> Q, int countFreshOranges)
{
//check out of bounds
//also check for no orange or already rotten
if (x < 0 || y < 0 || x >= grid.Length || y >= grid[0].Length || grid[x][y] == 2 || grid[x][y] == 0)
{
return countFreshOranges;
}
grid[x][y] = 2;
Q.Enqueue(new int[] { x, y });
countFreshOranges--;
return countFreshOranges;
}
}
}