Given a matrix of dimension m * n where each cell in the matrix can have values 0, 1, or 2 which has the following meaning:
0: Empty cell 1: Cells have fresh oranges 2: Cells have rotten oranges
So the task is to determine what is the minimum time required so that all the oranges become rotten. A rotten orange at index [i, j] can rot other fresh oranges at indexes [i – 1, j], [i + 1, j], [i, j – 1], [i, j + 1] (up, down, left and right). If it is impossible to rot every orange then simply return -1.
Examples:
Input: arr[][] = {
{2, 1, 0, 2, 1},
{1, 0, 1, 2, 1},
{1, 0, 0, 2, 1}};
Output: 2
In the first unit of time, all the oranges will be rotten
except the first orange of the last row
which will get rotten in the second unit of time.Input: arr[][] =
{{2, 1, 0, 2, 1},
{0, 0, 1, 2, 1},
{1, 0, 0, 2, 1}};
Output: -1
Approach: A BFS-based approach has been discussed here.
In this post, we solve the problem using Dynamic Programming.
Every orange needs to be rotten. Any orange can be rotten by its nearest rotten orange. So, for every orange which is not rotten yet, we find its minimum distance from rotten orange, Then we take the maximum of all which will represent the minimum time required to rot all oranges.
Let dp(i, j) = Minimum Distance of this orange from any rotten orange So, the DP states will be:
dp(i, j) = 0 if arr[i][j] == 2
dp(i, j) = INT_MAX if arr[i][j] == 0if dp(i, j) >0 and dp(i, j)<INT_MAX
then dp(i, j) = min(dp(i, j) , 1 + min(dp(i + 1, j),
dp(i – 1, j), dp(i, j + 1), dp(i, j – 1)))else dp(i, j) = 1 + min(dp(i + 1, j), dp(i – 1, j), dp(i, j + 1), dp(i, j – 1))
And our answer will be max(dp(i, j)) for all i, j where arr[i][j] == 1.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <iostream>using namespace std;#define C 5#define R 3#define INT_MAX 10000000// DP table to memoize the valuesint table[R][C] = { 0 };// Visited array to keep// track of visited nodes// in order to avoid infinite loopsint visited[R][C] = { 0 };// Function to return the// minimum of four numbersint min(int p, int q, int r, int s){ int temp1 = p < q ? p : q; int temp2 = r < s ? r : s; if (temp1 < temp2) return temp1; return temp2;}// Function to return the minimum distance// to any rotten orange from [i, j]int Distance(int arr[R][C], int i, int j){ // If i, j lie outside the array if (i >= R || j >= C || i < 0 || j < 0) return INT_MAX; // If 0 then it can't lead to // any path so return INT_MAX else if (arr[i][j] == 0) { table[i][j] = INT_MAX; return INT_MAX; } // If 2 then we have reached // our rotten oranges // so return from here else if (arr[i][j] == 2) { table[i][j] = 0; return 0; } // If this node is already visited // then return to avoid infinite loops else if (visited[i][j]) { return INT_MAX; } else { // Mark the current node as visited visited[i][j] = 1; // Check in all four possible directions int temp1 = Distance(arr, i + 1, j); int temp2 = Distance(arr, i - 1, j); int temp3 = Distance(arr, i, j + 1); int temp4 = Distance(arr, i, j - 1); // Take the minimum of all int min_value = 1 + min(temp1, temp2, temp3, temp4); // If result already exists in the table // check if min_value is less // than existing value if (table[i][j] > 0 && table[i][j] < INT_MAX) { if (min_value < table[i][j]) table[i][j] = min_value; } else table[i][j] = min_value; visited[i][j] = 0; return table[i][j]; }}// Function to return the minimum time// required to rot all the orangesint minTime(int arr[][C]){ int max = 0; // Calculate the minimum // distances to any rotten // orange from all the fresh oranges for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (arr[i][j] == 1) Distance(arr, i, j); } } // Pick the maximum distance of fresh orange // to some rotten orange for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (arr[i][j] == 1 && table[i][j] > max) max = table[i][j]; } } // If all oranges can be rotten if (max < INT_MAX) return max; return -1;}// Driver Codeint main(){ int arr[R][C] = { { 2, 1, 0, 2, 1 }, { 0, 0, 1, 2, 1 }, { 1, 0, 0, 2, 1 } }; cout << minTime(arr); return 0;} |
Java
// Java implementation of the approachclass GFG { static int C = 5; static int R = 3; static int INT_MAX = 10000000; // DP table to memoize the values static int[][] table = new int[R][C]; // Visited array to keep // track of visited nodes // in order to avoid infinite loops static int[][] visited = new int[R][C]; // Function to return the // minimum of four numbers static int min(int p, int q, int r, int s) { int temp1 = p < q ? p : q; int temp2 = r < s ? r : s; if (temp1 < temp2) return temp1; return temp2; } // Function to return the // minimum distance // to any rotten orange from [i, j] static int Distance(int arr[][], int i, int j) { // If i, j lie outside the array if (i >= R || j >= C || i < 0 || j < 0) return INT_MAX; // If 0 then it can't lead to // any path so return INT_MAX else if (arr[i][j] == 0) { table[i][j] = INT_MAX; return INT_MAX; } // If 2 then we have reached // our rotten oranges // so return from here else if (arr[i][j] == 2) { table[i][j] = 0; return 0; } // If this node is already visited // then return to avoid // infinite loops else if (visited[i][j] == 1) { return INT_MAX; } else { // Mark the current node // as visited visited[i][j] = 1; // Check in all four // possible directions int temp1 = Distance(arr, i + 1, j); int temp2 = Distance(arr, i - 1, j); int temp3 = Distance(arr, i, j + 1); int temp4 = Distance(arr, i, j - 1); // Take the minimum of all int min_value = 1 + min(temp1, temp2, temp3, temp4); // If result already exists in // the table check if min_value // is less than existing value if (table[i][j] > 0 && table[i][j] < INT_MAX) { if (min_value < table[i][j]) table[i][j] = min_value; } else table[i][j] = min_value; visited[i][j] = 0; } return table[i][j]; } // Function to return the minimum time // required to rot all the oranges static int minTime(int arr[][]) { int max = 0; // Calculate the minimum // distances to any rotten // orange from all the fresh oranges for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (arr[i][j] == 1) Distance(arr, i, j); } } // Pick the maximum distance // of fresh orange // to some rotten orange for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (arr[i][j] == 1 && table[i][j] > max) max = table[i][j]; } } // If all oranges can be rotten if (max < INT_MAX) return max; return -1; } // Driver Code public static void main(String[] args) { int arr[][] = { { 2, 1, 0, 2, 1 }, { 0, 0, 1, 2, 1 }, { 1, 0, 0, 2, 1 } }; System.out.println(minTime(arr)); }}// This code is contributed by Rajput-Ji |
Python3
# Python 3 implementation of the approachC = 5R = 3INT_MAX = 10000000# DP table to memoize the valuestable = [[0 for i in range(C)] for j in range(R)]# Visited array to keep track# of visited nodes# in order to avoid infinite loopsvisited = [[0 for i in range(C)] for j in range(R)]# Function to return the# minimum of four numbersdef min(p, q, r, s): if(p < q): temp1 = p else: temp1 = q if(r < s): temp2 = r else: temp2 = s if (temp1 < temp2): return temp1 return temp2# Function to return the# minimum distance# to any rotten orange from [i, j]def Distance(arr, i, j): # If i, j lie outside the array if (i >= R or j >= C or i < 0 or j < 0): return INT_MAX # If 0 then it can't lead to # any path so return INT_MAX elif (arr[i][j] == 0): table[i][j] = INT_MAX return INT_MAX # If 2 then we have reached # our rotten oranges # so return from here elif (arr[i][j] == 2): table[i][j] = 0 return 0 # If this node is already visited # then return to avoid infinite loops elif (visited[i][j]): return INT_MAX else: # Mark the current node as visited visited[i][j] = 1 # Check in all four # possible directions temp1 = Distance(arr, i + 1, j) temp2 = Distance(arr, i - 1, j) temp3 = Distance(arr, i, j + 1) temp4 = Distance(arr, i, j - 1) # Take the minimum of all min_value = 1 + min(temp1, temp2, temp3, temp4) if table[i][j] > 0 and \ table[i][j] < INT_MAX: if min_value < table[i][j]: table[i][j] = min_value else: table[i][j] = min_value visited[i][j] = 0 return table[i][j]# Function to return the minimum time# required to rot all the orangesdef minTime(arr): max = 0 # Calculate the minimum distances # to any rotten # orange from all the fresh oranges for i in range(R): for j in range(C): if (arr[i][j] == 1): Distance(arr, i, j) # Pick the maximum distance # of fresh orange # to some rotten orange for i in range(R): for j in range(C): if (arr[i][j] == 1 and table[i][j] > max): max = table[i][j] # If all oranges can be rotten if (max < INT_MAX): return max return -1# Driver Codeif __name__ == '__main__': arr = [[2, 1, 0, 2, 1], [0, 0, 1, 2, 1], [1, 0, 0, 2, 1]] print(minTime(arr)) |
C#
// C# implementation of // the above approachusing System;class GFG{ static int C = 5;static int R = 3;static int INT_MAX = 10000000;// DP table to memoize // the valuesstatic int[,] table = new int[R, C];// Visited array to keep// track of visited nodes// in order to avoid infinite // loopsstatic int[,] visited = new int[R, C];// Function to return the// minimum of four numbersstatic int min(int p, int q, int r, int s){ int temp1 = p < q ? p : q; int temp2 = r < s ? r : s; if (temp1 < temp2) return temp1; return temp2;}// Function to return the// minimum distance// to any rotten orange // from [i, j]static int Distance(int [,]arr, int i, int j){ // If i, j lie outside // the array if (i >= R || j >= C || i < 0 || j < 0) return INT_MAX; // If 0 then it can't lead // to any path so return // INT_MAX else if (arr[i, j] == 0) { table[i, j] = INT_MAX; return INT_MAX; } // If 2 then we have reached // our rotten oranges // so return from here else if (arr[i, j] == 2) { table[i, j] = 0; return 0; } // If this node is already // visited then return to // avoid infinite loops else if (visited[i, j] == 1) { return INT_MAX; } else { // Mark the current node // as visited visited[i, j] = 1; // Check in all four // possible directions int temp1 = Distance(arr, i + 1, j); int temp2 = Distance(arr, i - 1, j); int temp3 = Distance(arr, i, j + 1); int temp4 = Distance(arr, i, j - 1); // Take the minimum of all int min_value = 1 + min(temp1, temp2, temp3, temp4); // If result already exists in // the table check if min_value // is less than existing value if (table[i, j] > 0 && table[i, j] < INT_MAX) { if (min_value < table[i, j]) table[i, j] = min_value; } else table[i, j] = min_value; visited[i, j] = 0; } return table[i, j];}// Function to return the minimum // time required to rot all the // orangesstatic int minTime(int [,]arr){ int max = 0; // Calculate the minimum // distances to any rotten // orange from all the fresh // oranges for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (arr[i, j] == 1) Distance(arr, i, j); } } // Pick the maximum distance // of fresh orange // to some rotten orange for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { if (arr[i, j] == 1 && table[i, j] > max) max = table[i, j]; } } // If all oranges can be // rotten if (max < INT_MAX) return max; return -1;}// Driver Codepublic static void Main(string[] args){ int [,]arr = {{2, 1, 0, 2, 1}, {0, 0, 1, 2, 1}, {1, 0, 0, 2, 1}}; Console.Write(minTime(arr));}}// This code is contributed by Chitranayal |
Javascript
<script>// Javascript implementation of the approach let C = 5;let R = 3;let INT_MAX = 10000000;// DP table to memoize the valueslet table = new Array(R);// Visited array to keep // track of visited nodes // in order to avoid infinite loopslet visited = new Array(R);for(let i = 0; i < R; i++){ table[i] = new Array(C); visited[i] = new Array(C);} // Function to return the // minimum of four numbers function min(p, q, r, s) { let temp1 = p < q ? p : q; let temp2 = r < s ? r : s; if (temp1 < temp2) return temp1; return temp2; } // Function to return the // minimum distance // to any rotten orange from [i, j] function Distance(arr, i, j) { // If i, j lie outside the array if (i >= R || j >= C || i < 0 || j < 0) return INT_MAX; // If 0 then it can't lead to // any path so return INT_MAX else if (arr[i][j] == 0) { table[i][j] = INT_MAX; return INT_MAX; } // If 2 then we have reached // our rotten oranges // so return from here else if (arr[i][j] == 2) { table[i][j] = 0; return 0; } // If this node is already visited // then return to avoid // infinite loops else if (visited[i][j] == 1) { return INT_MAX; } else { // Mark the current node // as visited visited[i][j] = 1; // Check in all four // possible directions let temp1 = Distance(arr, i + 1, j); let temp2 = Distance(arr, i - 1, j); let temp3 = Distance(arr, i, j + 1); let temp4 = Distance(arr, i, j - 1); // Take the minimum of all let min_value = 1 + min(temp1, temp2, temp3, temp4); // If result already exists in // the table check if min_value // is less than existing value if (table[i][j] > 0 && table[i][j] < INT_MAX) { if (min_value < table[i][j]) table[i][j] = min_value; } else table[i][j] = min_value; visited[i][j] = 0; } return table[i][j]; } // Function to return the minimum time // required to rot all the oranges function minTime(arr) { let max = 0; // Calculate the minimum // distances to any rotten // orange from all the fresh oranges for (let i = 0; i < R; i++) { for (let j = 0; j < C; j++) { if (arr[i][j] == 1) Distance(arr, i, j); } } // Pick the maximum distance // of fresh orange // to some rotten orange for (let i = 0; i < R; i++) { for (let j = 0; j < C; j++) { if (arr[i][j] == 1 && table[i][j] > max) max = table[i][j]; } } // If all oranges can be rotten if (max < INT_MAX) return max; return -1; } // Driver Code let arr = [[ 2, 1, 0, 2, 1],[0, 0, 1, 2, 1 ],[1, 0, 0, 2, 1]] document.write(minTime(arr));// This code is contributed by avanitrachhadiya2155</script> |
Output
-1
Time Complexity: O(R*C), where R and C are the number of rows and columns of the given arr[][]
Auxiliary Space: O(R*C)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
