Minimum time required to rot all oranges | Dynamic Programming | C ++ implementation of the approach ; DP table to memoize the values ; Visited array to keep track of visited nodes in order to avoid infinite loops ; Function to return the minimum of four numbers ; Function to return the minimum distance to any rotten orange from [ i , j ] ; If i , j lie outside the array ; If 0 then it can 't lead to  any path so return INT_MAX ; If 2 then we have reached our rotten oranges so return from here ; If this node is already visited then return to avoid infinite loops ; Mark the current node as visited ; Check in all four possible directions ; Take the minimum of all ; If result already exists in the table check if min_value is less than existing value ; Function to return the minimum time required to rot all the oranges ; Calculate the minimum distances to any rotten orange from all the fresh oranges ; Pick the maximum distance of fresh orange to some rotten orange ; If all oranges can be rotten ; Driver Code
#include <iostream> NEW_LINE using namespace std ; #define C  5 NEW_LINE #define R  3 NEW_LINE #define INT_MAX  10000000 NEW_LINE int table [ R ] [ C ] = { 0 } ; int visited [ R ] [ C ] = { 0 } ; 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 ; } int Distance ( int arr [ R ] [ C ] , int i , int j ) { if ( i >= R j >= C i < 0 j < 0 ) return INT_MAX ; else if ( arr [ i ] [ j ] == 0 ) { table [ i ] [ j ] = INT_MAX ; return INT_MAX ; } else if ( arr [ i ] [ j ] == 2 ) { table [ i ] [ j ] = 0 ; return 0 ; } else if ( visited [ i ] [ j ] ) { return INT_MAX ; } else { visited [ i ] [ j ] = 1 ; 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 ) ; int min_value = 1 + min ( temp1 , temp2 , temp3 , temp4 ) ; 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 ] ; } } int minTime ( int arr [ ] [ C ] ) { int max = 0 ; for ( int i = 0 ; i < R ; i ++ ) { for ( int j = 0 ; j < C ; j ++ ) { if ( arr [ i ] [ j ] == 1 ) Distance ( arr , i , j ) ; } } 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 ( max < INT_MAX ) return max ; return -1 ; } int 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 ; }