Maximum time required for all patients to get infected | Java program for the above approach ; Direction arrays ; Function to find the maximum time required for all patients to get infected ; Stores the number of rows ; Stores the number of columns ; Stores whether particular index ( i , j ) is visited or not ; Stores index and time of infection of infected persons ; Stores uninfected patients count ; Stores time at which last person got infected ; Traverse the matrix ; If the current patient is already infected ; Push the index of current patient and mark it as visited ; If current patient is uninfected increment uninfected count ; Iterate until queue becomes empty ; Stores the front element of queue ; Pop out the front element ; Check for all four adjacent indices ; Find the index of the adjacent cell ; If the current adjacent cell is invalid or it contains an infected patient ; Continue to the next neighbouring cell ; Push the infected neighbour into queue ; If an uninfected patient is present ; Return the final result ; Driver Code
import java . util . * ; public class GFG { static class pair { int first , second , third ; pair ( int first , int second , int third ) { this . first = first ; this . second = second ; this . third = third ; } } static int direction [ ] [ ] = { { 1 , 0 } , { 0 , - 1 } , { - 1 , 0 } , { 0 , 1 } } ; static int maximumTime ( int arr [ ] [ ] ) { int n = arr . length ; int m = arr [ 0 ] . length ; boolean visited [ ] [ ] = new boolean [ n ] [ m ] ; Queue < pair > q = new LinkedList < > ( ) ; int uninfected_count = 0 ; int time = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { if ( arr [ i ] [ j ] == 2 ) { q . add ( new pair ( i , j , 0 ) ) ; visited [ i ] [ j ] = true ; } if ( arr [ i ] [ j ] == 1 ) { uninfected_count ++ ; } } } while ( ! q . isEmpty ( ) ) { pair current = q . peek ( ) ; time = current . third ; q . poll ( ) ; for ( int [ ] it : direction ) { int i = current . first + it [ 0 ] ; int j = current . second + it [ 1 ] ; if ( i < 0 j < 0 i >= n j >= m arr [ i ] [ j ] != 1 visited [ i ] [ j ] ) { continue ; } q . add ( new pair ( i , j , time + 1 ) ) ; visited [ i ] [ j ] = true ; uninfected_count -- ; } } if ( uninfected_count != 0 ) return - 1 ; return time ; } public static void main ( String args [ ] ) { int arr [ ] [ ] = { { 2 , 1 , 0 , 2 , 1 } , { 1 , 0 , 1 , 2 , 1 } , { 1 , 0 , 0 , 2 , 1 } } ; System . out . println ( maximumTime ( arr ) ) ; } }