Minimum time required to rot all oranges | Dynamic Programming | Python 3 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
C = 5 NEW_LINE R = 3 NEW_LINE INT_MAX = 10000000 NEW_LINE table = [ [ 0 for i in range ( C ) ] for j in range ( R ) ] NEW_LINE visited = [ [ 0 for i in range ( C ) ] for j in range ( R ) ] NEW_LINE def min ( p , q , r , s ) : NEW_LINE INDENT if ( p < q ) : NEW_LINE INDENT temp1 = p NEW_LINE DEDENT else : NEW_LINE INDENT temp1 = q NEW_LINE DEDENT if ( r < s ) : NEW_LINE INDENT temp2 = r NEW_LINE DEDENT else : NEW_LINE INDENT temp2 = s NEW_LINE DEDENT if ( temp1 < temp2 ) : NEW_LINE INDENT return temp1 NEW_LINE DEDENT return temp2 NEW_LINE DEDENT def Distance ( arr , i , j ) : NEW_LINE INDENT if ( i >= R or j >= C or i < 0 or j < 0 ) : NEW_LINE INDENT return INT_MAX NEW_LINE DEDENT elif ( arr [ i ] [ j ] == 0 ) : NEW_LINE INDENT table [ i ] [ j ] = INT_MAX NEW_LINE return INT_MAX NEW_LINE DEDENT elif ( arr [ i ] [ j ] == 2 ) : NEW_LINE INDENT table [ i ] [ j ] = 0 NEW_LINE return 0 NEW_LINE DEDENT elif ( visited [ i ] [ j ] ) : NEW_LINE INDENT return INT_MAX NEW_LINE DEDENT else : NEW_LINE INDENT visited [ i ] [ j ] = 1 NEW_LINE temp1 = Distance ( arr , i + 1 , j ) NEW_LINE temp2 = Distance ( arr , i - 1 , j ) NEW_LINE temp3 = Distance ( arr , i , j + 1 ) NEW_LINE temp4 = Distance ( arr , i , j - 1 ) NEW_LINE min_value = 1 + min ( temp1 , temp2 , temp3 , temp4 ) NEW_LINE if table [ i ] [ j ] > 0 and table [ i ] [ j ] < INT_MAX : NEW_LINE INDENT if min_value < table [ i ] [ j ] : NEW_LINE INDENT table [ i ] [ j ] = min_value NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT table [ i ] [ j ] = min_value NEW_LINE DEDENT visited [ i ] [ j ] = 0 NEW_LINE DEDENT return table [ i ] [ j ] NEW_LINE DEDENT def minTime ( arr ) : NEW_LINE INDENT max = 0 NEW_LINE for i in range ( R ) : NEW_LINE INDENT for j in range ( C ) : NEW_LINE INDENT if ( arr [ i ] [ j ] == 1 ) : NEW_LINE INDENT Distance ( arr , i , j ) NEW_LINE DEDENT DEDENT DEDENT for i in range ( R ) : NEW_LINE INDENT for j in range ( C ) : NEW_LINE INDENT if ( arr [ i ] [ j ] == 1 and table [ i ] [ j ] > max ) : NEW_LINE INDENT max = table [ i ] [ j ] NEW_LINE DEDENT DEDENT DEDENT if ( max < INT_MAX ) : NEW_LINE INDENT return max NEW_LINE DEDENT return - 1 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ [ 2 , 1 , 0 , 2 , 1 ] , [ 0 , 0 , 1 , 2 , 1 ] , [ 1 , 0 , 0 , 2 , 1 ] ] NEW_LINE print ( minTime ( arr ) ) NEW_LINE DEDENT